代码随想录算法训练营第55天 [ 42. 接雨水 84.柱状图中最大的矩形]
一、42. 接雨水
链接: 代码随想录.
思路：找到左边第一个大于我的和右边第一个大于我的
做题状态：看解析后做出来了
//暴力法（会超时）
class Solution {
public:int trap(vector<int>& height) {int sum = 0;for (int i = 0; i < height.size(); i++) {if (i == 0 || i == height.size() - 1) {continue;}int lHeight = height[i];int rHeight = height[i];for (int l = i - 1; l >= 0; l--) {lHeight = max(lHeight, height[l]);}for (int r = i + 1; r < height.size(); r++) {rHeight = max(rHeight, height[r]);}int res = min(lHeight, rHeight) - height[i];// if (res > 0) {sum += res;// }}return sum;}
};
//双指针法
class Solution {
public:int trap(vector<int>& height) {int sum = 0;int size = height.size();vector<int> maxLeft(size, 0);vector<int> maxRight(size);// 每个柱子 左边的柱子的最大高度maxLeft[0] = height[0];for (int i = 1; i < size; i++) {maxLeft[i] = max(height[i], maxLeft[i - 1]);}// 每个柱子 右边的柱子的最大高度maxRight[size - 1] = height[size - 1];for (int i = size - 2; i >= 0; i--) {maxRight[i] = max(height[i], maxRight[i + 1]);}// 求和for (int i = 0; i < size; i++) {int count = min(maxLeft[i], maxRight[i]) - height[i];sum += count;}return sum;}
};
//单调栈法
class Solution {
public:int trap(vector<int>& height) {stack<int> st;int sum = 0;// 先把左边界放入栈中st.push(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()]) {// 当前栈顶元素是中间的元素int mid = st.top();st.pop();// 上面又pop了一次，需要保证栈不为空if (!st.empty()) {// pop后栈顶元素是左边界的下标，i是有边界的下标，左边界和有边界高度的最小值// 减去 mid的高度，得到能装多少雨水的高度int h = min(height[st.top()], height[i]) - height[mid];// 再得到雨水的宽度int w = i - st.top() - 1;// 收集结果sum += h * w;}}st.push(i);}}return sum;}
};
二、84.柱状图中最大的矩形
链接: 代码随想录.
思路：找到左边第一个小于我的和右边第一个小于我的，区间左右都要添加一个0，防止单纯的递增heights或者单纯递减的heights没办法收集答案
做题状态：看解析后做出来了
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 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 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;}
};