單調棧
使用場景：通常是一維數組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置
本質：空間換時間
三個判斷條件：
當前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況
當前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況
當前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況
739. 每日溫度
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int>s;
vector<int>result(temperatures.size(), 0);
s.push(0);
int index = 1;
while(index < temperatures.size()){
while(!s.empty() && temperatures[s.top()] < temperatures[index]){
int temp = s.top();
s.pop();
result[temp] = index - temp;
}
s.push(index);
index++;
}
return result;
}
};
496. 下一個更大元素 I
題目： 給你兩個 沒有重復元素 的數組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
請你找出 nums1 中每個元素在 nums2 中的下一個比其大的值。
思路 ： num2作單調棧找下一個大的值，彈出時，判斷是否在num1中出現過，如果出現則進行賦值，鏈接使用unordered_map
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int>result(nums1.size(), -1);
unordered_map<int, int>m;
stack<int>s;
for(int i=0; i<nums1.size();i++){
m[nums1[i]] = i;
}
s.push(0);
int index = 1;
while(index < nums2.size()){
while(!s.empty() && nums2[s.top()] < nums2[index]){ //彈出時判斷
if(m.find(nums2[s.top()]) != m.end()){
result[m[nums2[s.top()]]] = nums2[index];
}
s.pop();
}
s.push(index);
index++;
}
return result;
}
};
503. 下一個更大元素 II
題目：循環(huán)數組
簡單版： 兩個數組拼接在一起，然后使用單調棧求下一個最大值
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int>result(n , -1);
for(int i=0; i<n; i++) nums.push_back(nums[i]);
stack<int>s;
s.push(0);
for(int i=1; i<nums.size(); i++){
while(!s.empty() && nums[s.top()] < nums[i]){
if(s.top()<n){
result[s.top()] = nums[i];
}
s.pop();
}
s.push(i);
}
return result;
}
};
改進版： 不擴充nums，而是在遍歷的過程中模擬走了兩邊nums
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int>result(n , -1);
stack<int>s;
s.push(0);
for(int i=1; i<n*2; i++){
while(!s.empty() && nums[s.top()%n] < nums[i%n]){
if(s.top()<n){
result[s.top()] = nums[i%n];
}
s.pop();
}
s.push(i);
}
return result;
}
};
42. 接雨水
- 暴力
思路：如果按照列來計算的話，寬度一定是1了，我們再把每一列的雨水的高度求出來就可以了
每一列雨水的高度，取決于，該列左側最高的柱子和右側最高的柱子中最矮的那個柱子的高度。
問題：復雜度為O(n^2) 超時
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
for(int i=1; i<height.size()-1; i++){
int left = 0;
int right = 0;
for(int j=i; j>=0; j--){
left = max(left, height[j]);
}
for(int j=i; j<height.size(); j++){
right = max(right, height[j]);
}
sum += min(left, right) - height[i];
}
return sum;
}
};
2.雙指針改進暴力 空間換時間 提前將左右最高高度算出來
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
vector<int>left(height.size(), 0);
vector<int>right(height.size(), 0);
int m_left = height[0];
int m_right = height[height.size()-1];
for(int i=0; i<height.size(); i++){
m_left = max(m_left, height[i]);
left[i] = m_left;
}
for(int i=height.size()-1; i>=0; i--){
m_right = max(m_right, height[i]);
right[i] = m_right;
}
for(int i=1; i<height.size()-1; i++){
sum += min(left[i], right[i]) - height[i];
}
return sum;
}
};
- 雙指針
思路：
單調棧是按照行方向來計算雨水
棧頂和棧頂的下一個元素以及要入棧的元素，三個元素來接水
雨水高度是 min(凹槽左邊高度, 凹槽右邊高度) - 凹槽底部高度
水的寬度是 凹槽右邊的下標 - 凹槽左邊的下標 - 1
class Solution {
public:
int trap(vector<int>& height) {
stack<int>s;
int sum = 0;
s.push(0);
for(int i=1; i<height.size(); i++){
while(!s.empty() && height[s.top()] < height[i]){
int cur = s.top();
s.pop();
if(!s.empty()){ //來避免 棧內[2] 元素3 村水量 0 只要彈出就可以了
int h = min(height[i], height[s.top()]) - height[cur];
sum += h * (i-s.top()-1);
}
}
s.push(i);
}
return sum;
}
};
84. 柱狀圖中最大的矩形
題目給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。
主體思路：
每一個位置能達到的最大面積取決于它左右兩側小于它的高度位置。
int w = right-left - 1;
int h = heights[i];
sum = max(sum, w*h);
暴力超時
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int sum = 0;
for(int i=0; i<heights.size(); i++){
int left = i;
int right = i;
while(left >= 0){
if(heights[left] < heights[i]) break;
left--;
}
while(right < heights.size()){
if(heights[right] < heights[i]) break;
right++;
}
int w = right-left - 1;
int h = heights[i];
sum = max(sum, w*h);
}
return sum;
}
};
雙指針優(yōu)化，空間換時間，提前記錄左右兩側的位置信息沒有數組保存時，需要一個一個跳進行比較。有數組后，那么可以利用之前的比較信息進行跳著比較。
heights[left] >= heights[i]) 時
直接跳到 left[left]指向的位置
注意
left是往左跳 則遍歷順序從左到右
right 向右跳，則右邊的先算，遍歷順序從右向左文章來源：http://www.zghlxwxcb.cn/news/detail-620937.html
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int>left(n, -1);
vector<int>right(n, n);
for(int i=0; i<n; i++){
int l = i-1;
while(l>=0 && (heights[l] >= heights[i])) l = left[l];
left[i] = l;
}
for(int i=n-1; i>=0; i--){
int r = i+1;
while(r < n && (heights[r] >= heights[i])) r = right[r];
right[i] =r;
}
int sum=0;
for(int i=0; i<n; i++){
sum = max(sum, heights[i] *(right[i]-left[i]-1));
}
return sum;
}
};
單調棧：目的找到左右兩側第一個比它小的元素
棧內元素從小到大，
當前元素小于棧頂元素時， 當前元素就是右邊界，棧頂元素的下一個元素就是左邊界， w = right - left - 1 h = height[s.top()] sum = max(sum, h*w）
注意兩種情況文章來源地址http://www.zghlxwxcb.cn/news/detail-620937.html
- 2 3 4 5 遞增序列沒有機會彈出 所以在最后面加入一個0 —> 2 3 4 5 0
- 8 7 6 5 第一個元素沒有左邊界 所以在最前面加入一個0 —> 0 8 7 6 5
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
heights.insert(heights.begin(), 0);
int n = heights.size();
stack<int>s;
s.push(0);
int sum = 0;
for(int i=1; i<n; i++){
if(heights[i] > heights[s.top()]){
s.push(i);
}else if(heights[i] == heights[s.top()]){
s.pop();
s.push(i);
}else{
while(!s.empty() && (heights[i] < heights[s.top()])){
int mid = s.top();
s.pop();
if(!s.empty()){
int left = s.top();
int w = i-left-1;
int h = heights[mid];
sum = max(sum, w*h);
}
}
s.push(i);
}
}
return sum;
}
};
到了這里，關于day58 單調棧的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
