Leetcode P84 Java使用栈解决此问题

Leetcode P84 Java使用栈解决此问题

执行用时：22 ms, 在所有 Java 提交中击败了69.98%的用户

内存消耗：54.5 MB, 在所有 Java 提交中击败了54.50%的用户

通过测试用例：98 / 98

ideas

​ 首先创建一个操作数组用来帮助我们进行操作，还要创建一个栈，栈用存放每个元素所在的下标，为了方便计算宽度。

        int res =0 ;
        int n = heights.length;
        int[] arr = new int[n+2];
        System.arraycopy(heights,0,arr,1,n);
        /**
         * 栈中存放下标，方便计算宽度
         */
        Deque<Integer> stack = new ArrayDeque<>();
        int nOfArr = arr.length;
1
2
3
4
5
6
7
8
9

我们的操作数组长度多了2是因为我们要将0和nOfArr-1下标的元素设置为0为了方便帮助我们操作，也用来防止一些情况

这边两个位置设置0 主要防止

类似 4 5 这时候我们arr的值是0 4 5 0 这时候stack把5弹出（因为0小于5）

那么就是 5 *（3-1-1） = 5

接下来 4 * (3 - 0 - 1) = 8

比如 4 5 3 这时候arr就是 0 4 5 3 0 我们发现3比5小，那么5弹出

5 * (3 - 1 - 1) = 5

​ 4 * (3 - 0 - 1) = 8

接下来我们stack中的元素为 arr[0]: 0 ,arr[3]: 3

接下来发现0比3小，那么3弹出

​ 3 * (4 - 0 - 1) = 9

      arr[0] = arr[nOfArr-1] = 0;
1

接下来就进行判断，如果当前下标的高度小于栈顶的元素高度，那么就开始计算面积

        for (int i = 0; i < nOfArr; i++) {
            int h = arr[i];
            while (!stack.isEmpty() && h < arr[stack.peek()]){
                int tmph = arr[stack.pop()];
                res = Math.max(res,tmph * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
1
2
3
4
5
6
7
8

最终的res就是我们的答案

        return res;
1

Code

	 public int largestRectangleArea(int[] heights) {
        int res =0 ;
        int n = heights.length;
        int[] arr = new int[n+2];
        System.arraycopy(heights,0,arr,1,n);
        /**
         * 栈中存放下标，方便计算宽度
         */
        Deque<Integer> stack = new ArrayDeque<>();
        int nOfArr = arr.length;

        //这边两个位置设置0 主要防止
        // 类似  4 5 这时候我们arr的值是0 4 5 0 这时候stack把5弹出（因为0小于5）
        //      那么就是 5 *（3-1-1） = 5
        //      接下来   4 * (3 - 0 - 1) = 8
        // 比如  4 5 3 这时候arr就是 0 4 5 3 0 我们发现3比5小，那么5弹出
        //              5 * (3 - 1 - 1) = 5
        //              4 * (3 - 0 - 1) = 8
        // 接下来我们stack中的元素为 arr[0]: 0 ,arr[3]: 3
        // 接下来发现0比3小，那么3弹出
        //              3 * (4 - 0 - 1) = 9
        arr[0] = arr[nOfArr-1] = 0;

        for (int i = 0; i < nOfArr; i++) {
            int h = arr[i];
            while (!stack.isEmpty() && h < arr[stack.peek()]){
                int tmph = arr[stack.pop()];
                res = Math.max(res,tmph * (i - stack.peek() - 1));
            }
            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
22
23
24
25
26
27
28
29
30
31
32
33
34