题目描述

力扣题目链接
image.png

解题思路

具体参照：carl的题解
主要和接雨水不同的是求的是两边小于中间。

双指针（超时）

  1. /**
  2.         * 双指针法(超时)
  3.         *
  4.         * @param heights
  5.         * @return
  6.         */
  7. public int largestRectangleArea(int[] heights) {
  8.     int maxSize = 0;
  9.     for (int i = 0; i < heights.length; i++) {
  10.         int leftIndex = i;
  11.         int rightIndex = i;
  13.         // 找到小于i的高度
  14.         for (; leftIndex >= 0; leftIndex--) {
  15.             if (heights[leftIndex] < heights[i]) break;
  16.         }
  18.         for (; rightIndex < heights.length; rightIndex++) {
  19.             if (heights[rightIndex] < heights[i]) break;
  20.         }
  22.         int high = heights[i];
  23.         int width = rightIndex - leftIndex - 1;
  24.         maxSize = Math.max(maxSize, high * width);
  25.     }
  26.     return maxSize;
  27. }

动态规划

  1. /**
  2.         * 动态规划
  3.         *
  4.         * @param heights
  5.         * @return
  6.         */
  7. public int largestRectangleArea(int[] heights) {
  8.     int[] minLeftIndex = new int[heights.length];
  9.     int[] minRightIndex = new int[heights.length];
  10.     int maxSize = 0;
  12.     // 记录每个柱子 左边第一个小于该柱子的下标
  13.     minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
  14.     for (int i = 1; i < heights.length; i++) {
  15.         int t = i - 1;
  16.         // 这里不是用if，而是不断向左寻找的过程
  17.         while (t >= 0 && heights[t] >= heights[i])
  18.             t = minLeftIndex[t];    // while一直循环找到左边第一个小于该柱子的下标
  19.         minLeftIndex[i] = t;
  20.     }
  22.     minRightIndex[heights.length - 1] = heights.length;
  23.     for (int i = heights.length - 2; i >= 0; i--) {
  24.         int t = i + 1;
  25.         // 这里不是用if，而是不断向左寻找的过程
  26.         while (t < heights.length && heights[t] >= heights[i])
  27.             t = minRightIndex[t];      // 记录每个柱子 右边第一个小于该柱子的下标
  28.         minRightIndex[i] = t;
  29.     }
  31.     // 求和
  32.     for (int i = 0; i < heights.length; i++) {
  33.         int size = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
  34.         if (size > maxSize) maxSize = size;
  35.     }
  37.     return maxSize;
  38. }

⭐单调栈

  1. public int largestRectangleArea(int[] heights) {
  2.     // 数组扩容，在头尾各加一个元素
  3.     int[] array = new int[heights.length + 2];
  4.     array[0] = 0;
  5.     array[heights.length + 1] = 0;
  6.     for (int i = 0; i < heights.length; i++) {
  7.         array[i + 1] = heights[i];
  8.     }
  9.     Stack<Integer> stack = new Stack<>();
  10.     stack.push(0);  // 栈顶到栈底，从大到小
  11.     int maxSize = 0;
  13.     heights = array;    // 需要在头尾各加一个0，来保证大小为2或者1时特殊情况，和都是相同的数字也是特殊情况
  14.     for (int i = 1; i < heights.length; i++) {
  15.         if (heights[stack.peek()] < heights[i]) {
  16.             stack.push(i);
  17.         } else if (heights[stack.peek()] == heights[i]) {
  18.             stack.pop();
  19.             stack.push(i);
  20.         } else {
  21.             while (heights[stack.peek()] > heights[i]) {
  22.                 Integer mid = stack.peek();
  23.                 stack.pop();
  24.                 Integer left = stack.peek();
  25.                 int size = (i - left - 1) * heights[mid];
  26.                 maxSize = Math.max(size, maxSize);
  27.             }
  28.             stack.push(i);
  29.         }
  30.     }
  32.     return maxSize;
  33. }