太原城市建设招标网站,平台推广营销,2024年新闻时事热点论文,seo教程seo入门讲解代码随想录刷题60Day 目录
单调栈简介
单调栈的应用
下次更高温
下一个更大元素1
下一个更大元素2
接雨水
柱状图中最大矩形 单调栈简介
单调栈#xff08;Monotonic Stack#xff09;是一种特殊的栈数据结构#xff0c;它满足元素的单调性#xff0c;这种单调性需…代码随想录刷题60Day 目录
单调栈简介
单调栈的应用
下次更高温
下一个更大元素1
下一个更大元素2
接雨水
柱状图中最大矩形 单调栈简介
单调栈Monotonic Stack是一种特殊的栈数据结构它满足元素的单调性这种单调性需要自己建立和维护。单调栈分为单调递增栈和单调递减栈两种类型。
单调递增栈的特点是栈内元素从栈底到栈顶依次递增而单调递减栈则是栈内元素从栈底到栈顶依次递减。
单调栈的主要应用是解决一些与找到元素的下一个更大或更小相关的问题。它通过维护一个递增或递减的栈可以在常数时间内找到每个元素的下一个更大或更小的元素。
单调栈的基本操作包括
入栈将元素压入栈顶同时保持栈的单调性。
出栈从栈顶移除元素。
查找检查栈顶元素获取当前元素的下一个更大或更小的元素。
单调栈的应用
下次更高温 vectorint dailyTemperatures(vectorint temperatures) {int size temperatures.size();vectorint result(size, 0);stackint stack;stack.push(0);for (int i 1; i size; i){int j stack.top();if (temperatures[i] temperatures[j]){while (!stack.empty() temperatures[i] temperatures[j]){result[j] i - j;stack.pop();if (!stack.empty())j stack.top();}}stack.push(i);}return result;}
下一个更大元素1 vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {int size1 nums1.size();int size2 nums2.size();unordered_mapint, int umap;stackint stack;vectorint result;stack.push(0);for (int i 1; i size2; i){int j stack.top();if (nums2[j] nums2[i]){while (!stack.empty() nums2[j] nums2[i]){umap.insert(pairint, int(nums2[j], nums2[i]));stack.pop();if (!stack.empty())j stack.top();}}stack.push(i);}for (int i 0; i size1; i){if (umap.find(nums1[i]) ! umap.end())result.push_back(umap[nums1[i]]);elseresult.push_back(-1);}return result;}
下一个更大元素2 vectorint nextGreaterElements(vectorint nums) {int size nums.size();vectorint dp(size, -1);stackint mystack;mystack.push(0);for (int i 1; i size; i){if (nums[i] nums[mystack.top()]){while (!mystack.empty() nums[i] nums[mystack.top()]){dp[mystack.top()] nums[i];if (!mystack.empty())mystack.pop(); }}mystack.push(i);}for (int i 0; i size; i){if (nums[i] nums[mystack.top()]){while (!mystack.empty() nums[i] nums[mystack.top()]){dp[mystack.top()] nums[i];if (!mystack.empty())mystack.pop(); }}mystack.push(i);}return dp;}
接雨水 int trap(vectorint h){if (h.size() 3)return 0;stackint mystack;int result 0;mystack.push(0);for (int i 1; i h.size(); i){if (h[mystack.top()] h[i])mystack.push(i);else if (h[mystack.top()] h[i]){while (!mystack.empty() h[mystack.top()] h[i]){int mid mystack.top();mystack.pop();if (!mystack.empty())result (min(h[mystack.top()], h[i]) - h[mid]) * (i - mystack.top() - 1); }if (!mystack.empty() h[mystack.top()] h[i])mystack.pop();mystack.push(i);}else{mystack.pop();mystack.push(i);}}return result;}
柱状图中最大矩形 int largestRectangleArea(vectorint h) {h.push_back(0);int size h.size();stackint mystack;int result h[0];mystack.push(0);for (int i 1; i size; i){if (h[i] h[mystack.top()]){mystack.pop();}else if (h[i] h[mystack.top()]){int mid, left;while (!mystack.empty() h[i] h[mystack.top()]){mid mystack.top();mystack.pop();if (!mystack.empty())left mystack.top();elseleft -1;result max(result, (i - left - 1) * h[mid]);}}mystack.push(i);}return result;}
