代码随想录第46期 单调栈
这道题主要是单调栈的简单应用
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
vector<int> result(T.size(),0);
stack<int> st;
st.push(0);
for(int i=1;i<T.size();i++){
if(T[i]<=T[st.top()]){
st.push(i);
}else{
while(!st.empty()&&T[i]>T[st.top()]){
result[st.top()]=i-st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};
暴力模拟
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
for(int i=0;i<nums1.size();i++){
int j=0;
while(nums1[i]!=nums2[j]){
j++;
}
while(j<nums2.size()&&nums1[i]>=nums2[j]){
j++;
}
if(j>=nums2.size()){
result.push_back(-1);
}else{
int val=nums2[j];
result.push_back(val);
}
}
return result;
}
};单调栈
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> result(nums1.size(),-1);
stack<int> st;
st.push(0);
unordered_map<int, int> umap; // key:下标元素，value：下标
for (int i = 0; i < nums1.size(); i++) {
umap[nums1[i]] = i;
}
for(int i=1;i<nums2.size();i++){
if(nums2[i]<=nums2[st.top()]){
st.push(i);
}else{
while(!st.empty()&&nums2[i]>nums2[st.top()]){
if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
result[index] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return result;
}
};
比上一题多了个处理循环的操作
可以是模拟循环
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(),-1);
stack<int> st;
st.push(0);
for(int i=1;i<nums.size()*2;i++){
if(nums[i%nums.size()]<=nums[st.top()]){
st.push(i%nums.size());
}else{
while(!st.empty()&&nums[i%nums.size()]>nums[st.top()]){
result[st.top()]=nums[i%nums.size()];
st.pop();
}
st.push(i%nums.size());
}
}
// 最后再把结果集即result数组resize到原数组大小
result.resize(nums.size());
return result;
}
};也可以是直接扩充数组
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> nums1(nums.begin(), nums.end());
nums.insert(nums.end(), nums1.begin(), nums1.end());
vector<int> result(nums.size(),-1);
stack<int> st;
st.push(0);
unordered_map<int,int> umap;
for(int i=0;i<nums.size();i++){
if(nums[i]<=nums[st.top()]){
st.push(i);
}else{
while(!st.empty()&&nums[i]>nums[st.top()]){
result[st.top()]=nums[i];
umap[st.top()]=nums[i];
st.pop();
}
st.push(i);
}
}
// 最后再把结果集即result数组resize到原数组大小
result.resize(nums.size() / 2);
return result;
}
};
这道题同样是一个双指针问题
class Solution {
public:
int trap(vector<int>& nums) {
// max(min{左max,右max}-arr[i]，0)
//预处理最大值 left:0-0最大值 0-1最大 0-i最大值
// right:12-12最大值，11-12最大值 i-12最大值
/*int n=height.size();
int *lmax=new int[n];
int *rmax=new int[n];
lmax[0]=height[0];
for(int i=1;i<n;i++){
lmax[i]=max(lmax[i-1],height[i]);
}
rmax[n-1]=height[n-1];
for(int i=n-2;i>=0;i--){
rmax[i]=max(rmax[i+1],height[i]);
}
int ans=0;
for(int i=1;i<n-1;i++){
ans+=max(0,min(lmax[i-1],rmax[i+1])-height[i]);
}
return ans;*/
int l=0,r=nums.size()-1,lmax=nums[0],rmax=nums[nums.size()-1];
int ans=0;
while(l<=r){
if(lmax<=rmax){
ans+=max(0,lmax-nums[l]);
lmax=max(lmax,nums[l]);l++;
}else{
ans+=max(0,rmax-nums[r]);
rmax=max(rmax,nums[r]); r--;
}
}
return ans;
}
};
与上一题类似，但是更麻烦些
双指针解法
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> minLeftIndex(heights.size());
vector<int> minRightIndex(heights.size());
int size = heights.size();
// 记录每个柱子 左边第一个小于该柱子的下标
minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
for (int i = 1; i < size; i++) {
int t = i - 1;
// 这里不是用if，而是不断向左寻找的过程
while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
minLeftIndex[i] = t;
}
// 记录每个柱子 右边第一个小于该柱子的下标
minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环
for (int i = size - 2; i >= 0; i--) {
int t = i + 1;
// 这里不是用if，而是不断向右寻找的过程
while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
minRightIndex[i] = t;
}
// 求和
int result = 0;
for (int i = 0; i < size; i++) {
int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
result = max(sum, result);
}
return result;
}
};单调栈解法
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
// 第一个元素已经入栈，从下标1开始
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()]) { // 注意是while
int mid = st.top();
st.pop();
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = max(result, w * h);
}
}
st.push(i);
}
}
return result;
}
};
原文地址：https://blog.csdn.net/2302_79946078/article/details/143820533
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！