力扣爆刷第97天之hot100五连刷71-75

力扣爆刷第97天之hot100五连刷71-75

一、394. 字符串解码

题目链接：https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
思路：使用栈进行操作，如果是数字或者字母左括号直接进栈，否则开始出栈，出栈按数子拼接子串即可。

class Solution {
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;
        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                stk.removeLast();
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                while (repTime-- > 0) {
                    t.append(o);
                }
                stk.addLast(t.toString());
            }
        }

        return getString(stk);
    }

    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

二、739. 每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked
思路：求某一个数左边或者右边离他最近的一个大于或小于它的数，就使用单调栈，典型单调栈解法。

class Solution {
   public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < temperatures.length; i++) {
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int j = stack.pop();
                res[j] = i - j;
            }
            stack.push(i);
        }
        return res;
    }
}

三、84. 柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked
思路：典型单调栈，构造凸起，当前元素小于栈顶时，栈顶元素为凸起处，然后出栈，进行计算即可。

class Solution {
   public int largestRectangleArea(int[] heights) {
        int[] nums = new int[heights.length + 2];
        for(int i = 0; i < heights.length; i++) {
            nums[i+1] = heights[i];
        }
        heights = nums;
        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < heights.length; i++) {
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = heights[mid];
                max = Math.max(max, w * h);
            }
            stack.push(i);
        }
        return max;
    }
}

四、215. 数组中的第K个最大元素

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked
思路：桶排序，把所有元素分配到桶里，然后倒序遍历数够数直接返回。

class Solution {
  public int findKthLargest(int[] nums, int k) {
        // 桶排序
        int[] buckets = new int[20001];
        for(int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for(int i = buckets.length-1; i > 0; i--) {
            k = k - buckets[i];
            if(k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
    
    

}

五、347. 前 K 个高频元素

题目链接：https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked
思路：求前k个高频元素，先使用map去记录元素与元素出现的次数，然后使用优先级队列进行排序，最后收集即可。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1]-a[1]);
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
        }
        Set<Integer> set = map.keySet();
        Iterator<Integer> iter = set.iterator();
        for(int i = 0; i < set.size(); i++) {
            int key = iter.next();
            queue.add(new int[]{key, map.get(key)});
        }
        for(int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }
}