代码随想录 | Day 60（完结） - LeetCode 84. 柱状图中最大的矩形

        今天是单调栈的最后一天，延续了昨天的接雨水问题。只有一道题，同样3种解法。其中DP和单调栈解法难度都有提升，都需要对两端元素做特殊处理。重点是以前面的接雨水问题为模板，理解下这类问题的“左、中、右柱子确定矩形”的方法。另外今天也是最后一天了，紧紧张张也算赶上了，这60天虽然不容易，但也一转眼就过去了，完结撒花~

        第1题（LeetCode 84. 柱状图中最大的矩形）与day 59中第2题（LeetCode 42. 接雨水）很相似，同样有双指针、DP、单调栈这3种解法。

        双指针法相比接雨水，主要是从“找左、右两边各自最高的柱子”变成了“要找左、右两边各自第一个比当前柱子小的位置”，使其分别作为左、右边界（不包含在内），再令当前柱子的高作为矩形的高，两者相乘得到当前位置的矩形大小。所以在内部循环找“第一个比当前柱子小的位置”时，要先将柱子大小初始化为当前柱子高度，然后向左/右移动直至遇到更小值为止。当然，同样因为时间复杂度时O(n²)，所以会超时。

// 双指针
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        for (int i = 0; i < heights.size(); ++i) {
            int indLeft = i, indRight = i;
            while (indLeft >= 0 && heights[indLeft] >= heights[i]) {
                --indLeft;
            }
            while (indRight < heights.size() && heights[indRight] >= heights[i]) {
                ++indRight;
            }
            int w = indRight - indLeft - 1, h = heights[i];
            ans = max(ans, w * h);
        }
        return ans;
    }
};

        DP解法也与接雨水类似。由于最后矩形的宽是两下标之差再减1，所以这一题的难度主要增加在“dp数组要记录下标而不是柱子高度”。具体来说，两个p数组，indSmallerLeft[i]，indSmallerRight[i]分别代表位置i左、右两边第一个小于i位置柱子高度的柱子下标。所以对于位置i，其indSmallerLeft值就需要从(i - 1)开始不断通过indSmallerLeft表向左跳转，直到找到更小值（到0为止），其indSmallerRight值就需要从(i + 1)开始不断通过indSmallerRight表向右跳转，直到找到更小值（到heights表末尾为止）。

        初始化方面，indSmallerLeft和indSmallerRight需要分别初始化第0位和末尾位。第0位的左边界（不包含在内）应该是-1，末尾位的右边界（不包含在内）应该是“末尾 + 1”，所以indSmallerLeft[0]和indSmallerRight[height.size() - 1]分别初始化为-1和height.size()。indSmallerLeft和indSmallerRight在内层循环中需要使用while()。

// DP
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> indSmallerLeft(heights.size()), indSmallerRight(heights.size());
        indSmallerLeft[0] = -1;
        for (int i = 1; i < heights.size(); ++i) {
            int j = i - 1;
            while (j >= 0 && heights[j] >= heights[i]) {
                j = indSmallerLeft[j];
            }
            indSmallerLeft[i] = j;
        }
        indSmallerRight[heights.size() - 1] = heights.size();
        for (int i = heights.size() - 2; i >= 0; --i) {
            int j = i + 1;
            while (j < heights.size() && heights[j] >= heights[i]) {
                j = indSmallerRight[j];
            }
            indSmallerRight[i] = j;
        }
        int ans = 0;
        for (int i = 0; i < heights.size(); ++i) {
            int w = indSmallerRight[i]- indSmallerLeft[i] - 1, h = heights[i];
            ans = max(ans, w * h);
        }
        return ans;
    }
};

        单调栈解法相比接雨水有3点不同：

1. 栈从单调递减改为单调递增；
2. 矩形的高度需要更改为中间柱子的高度；
3. 接雨水问题中，左右两个端点的柱子永远不会有雨水，所以不会成为中间柱子。但这一题的左、右端点也可能成为中间柱子。然而此时左、右柱子右不存在。为此，要在heights前、后分别插入高度为0的柱子；

// 单调栈
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        int ans = 0;
        stack<int> st;
        st.push(0);
        for (int i = 1; i < heights.size(); ++i) {
            if (heights[i] > heights[st.top()]) {
                st.push(i);
            }
            else if (heights[i] == heights[st.top()]) {
                // st.pop();
                st.push(i);
            }
            else {
                while (!st.empty() && heights[i] < heights[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int w = i - st.top() - 1;
                        int h = heights[mid];
                        ans = max(ans, w * h);
                    }
                }
                st.push(i);
            }
        }
        return ans;
    }
};