84. 柱状图中最大的矩形

力扣链接(困难)：https://leetcode.cn/problems/largest-rectangle-in-histogram

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

个人题解

开始本题前，请先完成 42. 接雨水。

暴力法 \(O(N^2)\)

注意，本代码在力扣最新测试用例中会 TLE。

暴力法和接雨水类似，都是双指针的思想，只不过这里是求矩形面积而不是水坑面积，说直白点，接雨水是找凹槽，本题是找台阶。

如果左/右侧遇到一个比当前元素小的，那么很显然就不能组成矩形了，所以本题目标就是找到左/右侧第一个比当前元素小的元素下标，相减得到矩形的宽度，而高度自然就是当前元素的大小。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        for (int i = 0; i < heights.size(); i++) {
            // 双指针，找到左右两侧第一个比当前元素小的下标
            int l = i, r = i;
            while (l >= 0) {
                if (heights[l] < heights[i])
                    break;
                l--;
            }
            while (r < heights.size()) {
                if (heights[r] < heights[i])
                    break;
                r++;
            }
            int w = r - l - 1;
            int h = heights[i];
            result = max(result, w * h);
        }
        return result;
    }
};

双指针的优化 \(O(N)\)

注意，本代码中两次 for-while 嵌套并不是 \(O(N^2)\) 的时间复杂度，这是由于 while 循环中，l/r 每次并不是递减的操作而是跳跃操作，这个跳跃会直接让 l/r 指向 l/r 左/右侧第一个更小的元素的位置。

为什么这不是 \(O(N^2)\) ？以左侧遍历过程为例：

我们可以用“摊还分析”来理解。想象有两个指针，一个是外层循环的 i，另一个是内层循环的 l。

1. 指针 i 的移动：在整个 for 循环中，指针 i 从 1 移动到 n-1，总共前进了 n-1 步。我们可以把这看作是“存钱”。
2. 指针 l 的移动：对于每一次 for 循环，l 被初始化为 i-1。在 while 循环中，l 通过 l = lMinIdx[l] 的方式向左跳跃（值变小）。
3. 总成本分析：
   • l 的初始赋值 (l = i - 1) 总共发生了 n-1 次。
   • while 循环内部的跳跃 (l = lMinIdx[l]) 是在“花钱”。关键在于，指针 l 在整个算法生命周期内，向左跳跃的总次数是有限的。
   • l 的值最大为 n-2，最小为 -1。它从一个较大的 i-1 值开始，通过跳跃不断变小。每个索引值 j (0 <= j < n) 作为 l 的值，只会被访问并用于向左跳跃一次。之后 l 就会跳到比 j 更小的值，再也不会回到 j。
   • 因此，while 循环体内的语句在整个 for 循环的生命周期里，执行的总次数不会超过 n 次。

结论：for 循环本身提供了 \(O(N)\) 的基础复杂度。内部的 while 循环虽然看起来是嵌套的，但其总执行次数也被 \(O(N)\) 所限制。因此这一部分的总时间复杂度是 \(O(N) + O(N) \sim O(N)\)。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        // 记录左/右侧第一个小于当前元素的下标，避免重复寻找
        vector<int> lMinIdx(heights.size());
        vector<int> rMinIdx(heights.size());

        lMinIdx[0] = -1;
        for(int i = 1; i < heights.size(); i++) {
            int l = i - 1;
            // 如果不满足，则持续往左找
            // 需要把 lMinIdx[0] 赋值为负，使得 l == 0 时，下一次 while 不满足 l >= 0
            // 从而处理左边界情况，否则 l 永远不会越界
            while(l >= 0 && heights[l] >= heights[i]) l = lMinIdx[l];
            lMinIdx[i] = l;
        }
        // 右侧同理
        rMinIdx[heights.size() - 1] = heights.size();
        for(int i = heights.size() - 2; i >= 0; i--) {
            int r = i + 1;
            // 同理，需要把 rMinIdx[0] 赋值为 heights.size()
            // 使得 r == heights.size() 时，下一次 while 不满足 r < heights.size()
            // 从而处理右边界情况，否则 r 永远不会越界
            while(r < heights.size() && heights[r] >= heights[i]) r = rMinIdx[r];
            rMinIdx[i] = r;
        }

        for(int i = 0; i < heights.size(); i++) {
            int sum = heights[i] * (rMinIdx[i] - lMinIdx[i] - 1);
            result = max(result, sum);
        }

        return result;
    }
};

单调栈 \(O(N)\)

本题单调栈解法和 42. 接雨水 类似，接雨水是找凹槽，而本题是找山峰，但需要注意以下部分：

heights.insert(heights.begin(), 0);
heights.push_back(0);

上述操作是为了处理 height 数组为递增/递减时的情况。

试想，如果 height 数组是递增的，那么所有元素都会入栈，找不到任何一个元素比前一个入栈元素小的情况，自然无法触发 else 分支，永远无法计算面积，导致最终结果为 0。如果在末尾加上了 0，遍历到末尾时，就会触发 else 分支，得到正确的最大面积。

同理，如果 height 数组是递减的，假设为 [8, 6]，第一个元素 8 首先入栈，第二个元素 6 < 8 会认为此时找到了山峰，进入 else 逻辑，但 heights[i] < heights[st.top()] 显然是满足的，此时会将 8 出栈，这会导致单调栈为空，不满足 !st.empty() 无法进入计算面积逻辑。

随后又将元素 6 入栈，然而，后续已经没有其它元素可遍历了，所以得到最终面积为 0。如果在开头加入 0，则会发现在遍历到 6 时，会将 8 出栈，但此时单调栈并不为空，前面还有一个 0，可以正确进入面积计算逻辑，得到正确的结果。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);

        st.push(0);
        for (int i = 1; i < heights.size(); i++) {
            // 如果当前元素比栈顶大，则将其入栈
            // 反之则找到了峰，可以计算面积
            if (heights[i] >= heights[st.top()])
                st.push(i);
            else {
                // 如果栈顶元素比当前元素大，由于栈内元素单调递减，所以将栈顶元素出栈
                // 新的栈顶与当前元素之间组成一个山峰，出栈元素(mid)作为高度，计算面积
                while (!st.empty() && heights[i] < heights[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int l = st.top();
                        int r = i;
                        int w = r - l - 1;
                        int h = heights[mid];
                        result = max(result, w * h);
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};