栈

84. 柱状图中最大的矩形

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
     * 题目：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
     * 题解：
     * https://blog.csdn.net/Zolewit/article/details/88863970
     * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
     * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
     */
    @Test
    public void test() {
        System.out.println(largestRectangleArea1(new int[]{2, 1, 5, 6, 2, 3}));
        System.out.println(largestRectangleArea2(new int[]{2, 1, 5, 6, 2, 3}));
    }

    /**
     * 方法一
     * 固定中间一个找两边
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea1(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        // 最大面积
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int left = i;
            int currentHeight = heights[i];
            // left > 0 防止为第一个数据；寻找左边最后一个大于currentHeight的下标
            while (left > 0 && heights[left - 1] >= currentHeight) {
                left--;
            }
            int right = i;
            // right < heights.length - 1 防止为最后一个数据；寻找右边最后一个大于currentHeight的下标
            while (right < heights.length - 1 && heights[right + 1] >= currentHeight) {
                right++;
            }
            maxArea = Math.max(maxArea, (right - left + 1) * currentHeight);
        }
        return maxArea;
    }

    /**
     * 方法二
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea2(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        Deque<Integer> deque = new ArrayDeque<>(heights.length);
        deque.addLast(0);
        int maxArea = 0;
        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[i] < newHeights[deque.getLast()]) {
                int height = newHeights[deque.pollLast()];
                int width = i - deque.peekLast() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            deque.add(i);
        }
        return maxArea;
    }

这个题目的第二种解法真的太妙了，有亿点东西，我在idea中一步步调试才弄明白

队列

239. 滑动窗口最大值

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
     * 题目：https://leetcode-cn.com/problems/sliding-window-maximum/
     * 题解：https://leetcode.com/problems/sliding-window-maximum/discuss/65884/Java-O(n)-solution-using-deque-with-explanation
     */
    @Test
    public void test() {
        System.out.println(Arrays.toString(maxSlidingWindow1(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        System.out.println(Arrays.toString(maxSlidingWindow2(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }

    /**
     * 方法一：遍历每个滑动窗口
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        // nums.length - k + 1 : 滑动窗口个数
        int[] rnums = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            rnums[i] = max;
        }
        return rnums;
    }

    /**
     * 方法二：双端队列
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums.length + 1 - k];
        for (int i = 0; i < nums.length; i++) {
            // 每当新数进来时，如果发现队列头部的数的下标，是窗口最左边数的下标，则扔掉
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.poll();
            }
            // 把队列尾部所有比新数小的都扔掉，保证队列是降序的
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            // 加入新数
            deque.offerLast(i);
            // 队列头部就是该窗口内第一大的
            if ((i + 1) >= k) {
                res[i + 1 - k] = nums[deque.peek()];
            }
        }
        return res;
    }