代码随想录算法训练营 Day48 单调栈Ⅱ 接雨水Like
单调栈
题目
42. 接雨水 - 力扣（LeetCode）
单调栈解题，因为单调栈适合寻找一侧第一大的元素，我们使用递增栈实现，横向求解
栈内存放遍历过的元素（下标）
保持栈内数据单调递增（只需更小数据进入）
当数据大于栈口时找到了比当前元素右侧大的第一个元素，此时栈口的下一个元素时左侧大的元素
计算雨水高度：通过取两边柱子的最小值 - 底座高度实现
计算雨水宽度：左边下标 - 右边下标 - 1
一种特殊情况如果栈内若干个相同元素
此时计算的结果为 0（高度为 0）因此遇到重复元素弹出加入，建议弹出再加入减少计算
int trap(vector<int>& height) {// 定义栈 栈内存放元素下标std::stack<int> st;st.push(0);// 定义变量int sum = 0, h = 0, w = 0, mid = 0;// 单调栈遍历 采用单调递增栈for (int i = 1; i < height.size(); ++i) {if (height[i] < height[st.top()]) st.push(i);else if (height[i] == height[st.top()]) {st.pop();st.push(i); // 减少计算}else {while (!st.empty() && height[i] > height[st.top()]) {// 记录底柱mid = st.top();st.pop();if (!st.empty()) {// 记录左右最小柱子（左 st.top, 右 i）得到高和宽h = std::min(height[st.top()], height[i]) - height[mid];w = i - st.top() - 1;sum += h * w;}}st.push(i);}}return sum;
}
暴力双指针解题
纵向求解，只关注当前柱子的左高度与右高度，因此创建数组关注当前位置的左最大值与右最大值
只看右边，计算最大值数组，只看左边计算最大值数组
实际计算取最小元素，边界不存水 (i, n-1)
int trap(vector<int>& height) {// 数组存储int sum = 0;int n = height.size();std::vector<int> left(n, 0);left[0] = height[0];std::vector<int> right(n, 0);right[n-1] = height[n-1];// 寻找最大值 纵向计算只求当前雨水for (int i = 1; i < n-1; ++i) left[i] = std::max(left[i-1], height[i]);for (int i = n-2; i >= 0; --i) right[i] = std::max(right[i+1], height[i]);// 取最少容纳雨水for (int i = 1; i < n-1; ++i) sum += std::min(left[i], right[i]) - height[i];return sum;
}
终极双指针
TBC
84. 柱状图中最大的矩形 - 力扣（LeetCode）
使用单调栈求解柱子中左边比当前柱子矮的，右边比当前柱子矮的，求解最小值
使用单调递减单调栈实现，求左边比当前柱子小的 left，中间柱子 mid，右边比当前柱子小的 right
mid = st.top, st.pop() left = st.top right = i 单调递减栈存储比当前元素大的数据
w = right - left - 1
代码为接雨水的镜像版
特殊点
在元素中首尾添加一个 0，首的 0 用于处理输入第一次计算，尾的 0 用于处理最后一次计算
int largestRectangleArea(vector<int>& heights) {// 添加首尾 0 用于计算heights.insert(heights.begin(), 0);heights.push_back(0);// 定义单调栈 递减用于求小元素std::stack<int> st;st.push(0);// 定义元素int sum = 0, h = 0, w = 0, mid = 0, left = 0, right = 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()]) {mid = st.top();st.pop();if (!st.empty()) {left = st.top();right = i;h = heights[mid]; // 找到就是最低点w = right - left - 1;sum = std::max(sum, h * w);}}st.push(i);}}return sum;
}
双指针实现
类似接雨水只不过要寻找最小元素
寻找最小元素过程中在 for 内使用 while 遍历找到左边的第一个最小元素记录下标
面积为当前元素的高度乘以这个元素坐标和右边最小元素的宽度
寻找面积最小值即可
int largestRectangleArea(vector<int>& heights) {// 存储左右下标int n = heights.size();vector<int> leftIdx(n, 0);vector<int> rightIdx(n, 0);// 记录当前元素左边最小值leftIdx[0] = -1;for (int i = 1; i < n; ++i) {int t = i - 1;while (t >= 0 && heights[t] >= heights[i]) t = leftIdx[t];leftIdx[i] = t;}// 右边最小值rightIdx[n-1] = n;for (int i = n-2; i >= 0; --i) {int t = i + 1;while (t <= n-1 && heights[t] >= heights[i]) t = rightIdx[t];rightIdx[i] = t;}// 计算面积最大值int res = 0;for (int i = 0; i < n; ++i) {int sum = heights[i] * (rightIdx[i] - leftIdx[i] - 1);res = max(res, sum);}return res;
}