【每日刷题】栈与队列-随想录4、7、8、LC155、单调栈-LC739、单调栈-LC84

1. 随想录-4.LC20有效的括号

题解很妙。遍历到 [ { ( 的时候往stack里加入对应的 ] } )元素。遍历到右边元素的时候，就看栈顶弹出的元素是否一致。这解决了判断括号是否匹配问题。

但同时要注意数量问题！！两种情况

1. 左括号少，右括号多，遍历到最后，stack都空了，还有字符串字符每遍历完，所以必须要加的条件就是在if里加上 if (stack.isEmpty() || stack.pop() != c) 。先判断stack是否为空，省的stack.pop报空指针异常。
2. 左括号多，右括号少，字符串遍历结束了，stack里还有元素。所以最后要加判定条件，
   if (!stack.isEmpty()){ return false; }

代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if (c == '('){
                stack.push(')');
            }
            else if (c == '['){
                stack.push(']');
            }
            else if (c == '{'){
                stack.push('}');
            }
            else{
                if (stack.isEmpty() || stack.pop() != c){
                    return false;
                }
            }
        }
        if (!stack.isEmpty()){
            return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2. 随想录7.LC239.滑动窗口最大值

暴力解法：过不了（别看了）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] maxSlide = new int[nums.length-k+1];
        for (int left=0; left<=nums.length-k; left++){
            maxSlide[left] = maxFixed(nums, left, left+k-1);
        }
        return maxSlide;
    }

    public int maxFixed(int[] nums, int left, int right){
        int max = Integer.MIN_VALUE;
        for (int i=left; i<=right; i++){
            if (nums[i] > max){
                max = nums[i];
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

队列和栈方法。

中心思想：

遍历一个值，就把它插入到队列的末尾。但是如果队列末尾里有比它小的值，那必须把比它小的值都赶出去，再插入到末尾。因为比它小还比它先来，说明这个数已经失效了，怎么都不可能成为滑动窗口的最大值。这样能保证窗口的最大值永远在第一个。

维护一个数组，取每个窗口的队列的第一个值（即最大值）。

既要对队列的Last操作，又要对队列的First操作，所以用双端队列。

坑！！！
这道题搞了我两天，虽然最后我也不知道我当时写的方法哪里不对了，但是吧，就记住两点吧

1. 新来的值永远是插到队列的末尾，且前面不能有比它小的值，所以while那一块全是用的Last，不能用First ！！！
2. 形成窗口后滑动i从k开始遍历，i指向新进窗口的元素，别指窗口的第一个元素了，这样方便，也好看。
3. while里的第一个条件一定要判空！如果不判空的话后面的peekLast会报空指针异常。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        Deque<Integer> deque = new LinkedList<>();
        int[] array = new int[nums.length-k+1];
        
        //初始窗口
        for (int i=0; i<k; i++){
            while (!deque.isEmpty() && deque.peekLast()<nums[i]){
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
        }
        array[0] = deque.peekFirst();

        //形成窗口后滑动
        for (int i=k; i<nums.length; i++){
            if (nums[i-k] == deque.peekFirst()){
                deque.pollFirst();
            }
            while (!deque.isEmpty() && deque.peekLast()<nums[i]){
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
            array[i-k+1] = deque.peekFirst();
        }
        return array;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3.随想录8. LC347、前K个高频元素

题目链接
解法一：

1. 遍历一遍，建立哈希表存储数字与出现频次的映射。
2. 维护一个元素数目为k的小顶堆。（堆中存放的是元素，但是priority queue可以按照自定义顺序排序，自定义顺序为：元素的频次）。
3. 当有新元素来的时候，与堆顶元素作比较，若频次比堆顶元素大，则该元素应放到前k个高频元素中，所以堆顶元素出队列，该元素加队列。堆会自动按定义顺序排序。
4. 最终堆中的元素就是前K个高频元素。

时间复杂度：
建立哈希表：n；小顶堆本身维护：logk；遍历哈希，维护小顶堆：nlogk；遍历堆存进数组：k
所以整体时间复杂度为O(nlogk)

空间复杂度：
哈希表：n，小顶堆：k。
所以整体空间复杂度为O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //建立哈希表维护 数值与频次 的键值对
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums){
            if (map.containsKey(i)){
                map.put(i, map.get(i)+1);
            }else{
                map.put(i, 1);
            }
        }
        
        //定义PriorityQueue存放前k个高频元素
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return (map.get(a) - map.get(b));
            }
        });

        //遍历map,更新堆
        for (Integer key: map.keySet()){
            if (queue.size() < k){
                queue.offer(key);
            }else{
                if (map.get(key) > map.get(queue.peek())){
                    queue.poll();
                    queue.offer(key);
                }
            }
        }

        //输出堆元素
        int[] array = new int[k];
        for (int i=0; i<k; i++){
            array[i] = queue.poll();
        }
        return array;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

解法二：

1. 遍历一遍，建立哈希表存储数字与出现频次的映射。
2. 将Map.entrySet<>存放进list，list排序，按照自定义规则排序（按照频次，即value值从大到小排序）
3. 获取list中前k个元素的key值

时间复杂度：
建立哈希表：n；放进list：n；sort方法排序：nlogn；遍历堆存进数组：k
所以整体时间复杂度为O(nlogn)

空间复杂度：
O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //建立哈希表维护 数值与频次 的键值对
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums){
            if (map.containsKey(i)){
                map.put(i, map.get(i)+1);
            }else{
                map.put(i, 1);
            }
        }

		//将entryset放进list，对list进行排序
		List<Map.Entry<Integer, Integer>> list = new ArrayList<>();
		for (Map.Entry<Integer, Integer> entry: map.entrySet()){
			list.add(entry);
		}
		Collections.sort(list, (list1, list2) -> list2.getValue() - list1.getValue());

		//获取前k个值
		int[] array = new int[k];
        for (int i=0; i<k; i++){
            array[i] = list.get(i).getKey();
        }
        return array;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4. LC155.最小栈

多维护一个栈，记录当前最小。每放一个元素在栈里，就在另一个栈里记录下当前的最小值。

一个大坑，初始化stackMin的时候，stackMin.push(Integer.MAX_VALUE); push的是最大值而非最小值，这样之后比它小的才能被放进去。

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> stackMin;
    public MinStack() {
        stack = new Stack<Integer>();
        stackMin = new Stack<Integer>();
        stackMin.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        stackMin.push(Math.min(stackMin.peek(),val));
    }
    
    public void pop() {
        stack.pop();
        stackMin.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return stackMin.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

5. LC739.每日温度 （单调栈）

暴力解法（过不了）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        for (int i=0; i<temperatures.length; i++){
            if (findMax(temperatures, i) == -1){
                res[i] = 0;
            }else{
                res[i] = findMax(temperatures, i) - i;
            }
        }
        return res;
    }

    public int findMax(int[] temperatures, int start){
        for (int i=start+1; i<temperatures.length; i++){
            if (temperatures[i] > temperatures[start]){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

引入单调栈

单调栈使用场景：
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

单调栈的目的：
用一个栈记录我们已经遍历过的元素，这样新的元素来的时候，它就知道它比哪些曾经已遍历过的元素大，就可以做对应的操作了。

单调栈里存放的：
是数组下标。因为要求位置，存放数组下标可以更方便的定位位置的距离，如果对比数值的话，直接用数组下标也可以找到原数组中的数值。但如果存放的是数值的话，用数值去找下标就麻烦多了，且数值不唯一，找到的下标不一定是真实的下标。

单调栈的单调顺序：
顺序指的是从栈入口到栈底的顺序，下标对应的元素值是递增的还是递减的。
因为栈底的元素是先入栈的，它在等待后面有一个比它大的元素出现，然后它就能弹出了，所以栈底方向的元素一定是到目前为止最大的元素，也就是在遍历中还没有遇到一个元素在它的数组位置的右面出现，比它大。所以此题的单调顺序一定是递增的。

注意！！！stack和链表一样，都要判空！！while循环里一定要先判空

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<Integer>();
        for (int i=0; i<temperatures.length; i++){
            //其实这里没必要写
            if (stack.isEmpty()){
                stack.push(i);
                continue;
            }
            //栈顶的元素找到了它右边比它大的元素
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            //栈顶的元素比当前元素大，说明栈里的元素都还没有找到右边比它更大的了，继续等待
            stack.push(i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度为什么是O(n)？while那里也是循环，不应该是O(n^2)吗
chat老师的回答：

6. 柱状图中最大的矩形

题目链接

（贴个图好写题解）
首先具象理解一下题意：
对于5这个位置来说，利用它的高度可以得到的最大面积是：找到左边比它小的第一个位置，和右边比它小的第一个位置，位置的差值就是矩形的宽度，矩形的高度就是5本身的高度，所以5这个位置能取到的最大面积就是10（左边第一个小的是1，右边第一个小的是2）。
同理，对于6这个位置来说，利用它的高度可以得到的最大面积是：6（左边第一个小的是5，右边第一个小的是2）。
再同理，对于索引为1，高度为1的这个位置来说，利用它的高度可以得到的最大面积是：6（左边第一个小的是最左，右边第一个小的是最右）。
所以每个位置对应的可以得到的最大矩形面积求出来，比较大小，就知道了整个图形中最大的矩形面积是多少了。

接着分析：
对于每个位置，核心问题是找到其右边的第一个比它小的值，和左边第一个比它小的值，符合单调栈条件，所以用单调栈解题。
用单调递增还是递减的栈呢？因为要找比其小的值，栈底的元素先遍历，在栈底，说明到现在还没有找到比它更小的，所以可知，栈底的元素是最小的，所以栈顶的元素是最大的，所以是单调递减栈。

对于每个位置：
有三个重要变量。middle（当前位置），left（左边第一个小值），right（右边第一个小值）。

模拟一个过程：
假设当前栈里的元素是：1
遍历到了5，5比1大，所以入栈。（栈元素：51）
继续遍历6，6比5大，继续入栈。（栈元素：651）
继续遍历2，2比6小，此时6找到了其right。所以6出栈，mid是6，right是2，left是6出栈后的栈顶元素，left是5。那么6这个元素对应的利用6这个高度可以构成的最大矩形面积，就是（2的索引-5的索引-1）得到的矩形宽，×上6这个高。
6出栈后，继续比较，2比5小，则5也找到了它的right。所以5出栈，mid是5，right是2，left是1。5出栈。（栈元素：21）

前后加0：
问题来了，遍历到最后，栈内元素：321。怎么继续求3的right呢，数组末尾加0，也就是再进来个0，把3赶出去。
然后2也被赶出去了。
1也被赶出去了，但是1的left怎么算呢，数组开头加0，则栈底永远是0,1的left也可以计算了。

当然，最后，别忘了栈内存放的元素是索引。
完。

代码
注意！！

1. largeArea 最好初始化为0，而不是Integer.MIN_VALUE，因为会有heights =[0]的情况。
2. while循环里，不考虑相等的情况。也不能把相等的情况划分到小于或者大于里去探讨，至于为什么，想想（1,5，5,5，2）这种情况就知道了。这几个5的高度都是一样的，求它们整体的left和right就可以了，mid是谁都无所谓。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int largeArea = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int[] heightsAppend = new int[heights.length+2];
        heightsAppend[0] = 0;
        heightsAppend[heightsAppend.length-1] = 0;
        //数组首尾加0
        for (int i=0; i<heights.length; i++){
            heightsAppend[i+1] = heights[i];
        }
        //开始正式遍历
        stack.push(0);
        for (int i=1; i<heightsAppend.length; i++){
            //遍历元素大于栈顶元素，符合单调递减，入栈
            if (heightsAppend[i] > heightsAppend[stack.peek()]){
                stack.push(i);
            }
            //遍历元素小于栈顶元素
            else{
                while (heightsAppend[i] < heightsAppend[stack.peek()]){
                    int mid = stack.pop();
                    int right = i;
                    int left = stack.peek();
                    largeArea = Math.max(largeArea, (right-left-1)*heightsAppend[mid]);
                }
                stack.push(i);
            }
        }
        return largeArea;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32