leetcode 84. Largest Rectangle in Histogram | 84. 柱状图中最大的矩形（单调栈）

深碍√TFBOYSˉ_ 2022-09-11 09:21 127阅读 0赞

## 题目 ##

[https://leetcode.com/problems/largest-rectangle-in-histogram/][https_leetcode.com_problems_largest-rectangle-in-histogram]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

一句话总结：遍历数组，对于每个height\[i\]，以其自身的高度顶到头，然后分别向左右扩张到极限作为当前面积，找到最大者。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
所以，根据上面所说，我们需要维护 **左边第一个小于 i 的元素的下标、右边第一个小于 i 的元素的下标**。

需要分别从左到右、从右到左，维护单调栈。可以参考：[  
leetcode 496, 503, 556. Next Greater Element I, II, III | 496, 503, 556. 下一个更大元素 I,II,III（单调栈）][leetcode 496_ 503_ 556. Next Greater Element I_ II_ III _ 496_ 503_ 556. _ I_II_III]，只不过本题是找到下一个更小的元素。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

class Solution { 
        public int largestRectangleArea(int[] heights) { 
            int L = heights.length;
            // 找左边第一个小于h[i]的数
            // 从右向左遍历，维护单调不减栈，小数h[i]不断将大数h[j]弹出，则h[i]左边第一个小于h[i]的数为h[j]
            Stack<Integer> valueStack = new Stack<>();
            Stack<Integer> indexStack = new Stack<>();
            int[] leftIndex = new int[L]; // i左边第一个小于i的数的下标
            Arrays.fill(leftIndex, -1);
            for (int i = L - 1; i >= 0; i--) { 
                while (!valueStack.isEmpty() && valueStack.peek() > heights[i]) { 
                    leftIndex[indexStack.pop()] = i;
                    valueStack.pop();
                }
                valueStack.push(heights[i]);
                indexStack.push(i);
            }
            // 找右边第一个小于h[i]的数
            // 从左向右遍历，维护单调不减栈
            valueStack = new Stack<>();
            indexStack = new Stack<>();
            int[] rightIndex = new int[L]; // i右边第一个小于i的数的下标
            Arrays.fill(rightIndex, L);
            for (int i = 0; i < L; i++) { 
                while (!valueStack.isEmpty() && valueStack.peek() > heights[i]) { 
                    rightIndex[indexStack.pop()] = i;
                    valueStack.pop();
                }
                valueStack.push(heights[i]);
                indexStack.push(i);
            }
    
            // 对于每个h[i]，以其自身的高度，分别向左右扩张
            int maxArea = 0;
            for (int i = 0; i < L; i++) { 
                maxArea = Math.max(maxArea, (rightIndex[i] - leftIndex[i] - 1) * heights[i]);
            }
            return maxArea;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[https_leetcode.com_problems_largest-rectangle-in-histogram]: https://leetcode.com/problems/largest-rectangle-in-histogram/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/dc5f4ed7f78045e3904c47f4ac5a6307.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/dfd18d0f9df1479a8125425c21d20d78.png
[leetcode 496_ 503_ 556. Next Greater Element I_ II_ III _ 496_ 503_ 556. _ I_II_III]: https://hanquan.blog.csdn.net/article/details/120284832
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/1809e1c6d6c148ff9ea8cadbec16a7ce.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/bee39011e84a4017890a4f8285e5f492.png