您的位置:首页 > 财经 > 产业 > 代码随想录leetcode200题之单调栈

代码随想录leetcode200题之单调栈

2024/12/23 11:35:16 来源:https://blog.csdn.net/YMWM_/article/details/139887626  浏览:    关键词:代码随想录leetcode200题之单调栈

目录

  • 1 介绍
  • 2 训练
  • 3 参考

1 介绍

本博客用来记录代码随想录leetcode200题之单调栈相关题目。

2 训练

题目1:739. 每日温度

解题思路:单调栈模型–找到数组中下一个更大数。从右到左遍历,保留更大值,因此是一个单调递减的栈。

C++代码如下,

class Solution {
public:vector<int> dailyTemperatures(vector<int>& a) {int n = a.size();vector<int> res(n, 0);stack<int> stk;for (int i = n-1; i >= 0; --i) {while (!stk.empty() && a[stk.top()] <= a[i]) {stk.pop();}if (!stk.empty()) {res[i] = stk.top() - i;}stk.push(i);}return res;}
};

python3代码如下,

class Solution:def dailyTemperatures(self, a: List[int]) -> List[int]:n = len(a)stk = []res = [0] * n for i in range(n-1,-1,-1):while len(stk) > 0 and a[stk[-1]] <= a[i]:del stk[-1]if len(stk) > 0:res[i] = stk[-1] - i stk.append(i)return res 

题目2:496. 下一个更大元素 I

解题思路:单调栈模型,数组中下一个更大的数。

C++代码如下,

class Solution {
public:vector<int> nextGreaterElement(vector<int>& a, vector<int>& b) {int n = b.size();stack<int> stk;unordered_map<int, int> map_x_y;for (int i = n-1; i >= 0; --i) {while (!stk.empty() && b[stk.top()] <= b[i]) {stk.pop();}if (!stk.empty()) {map_x_y[b[i]] = b[stk.top()];}stk.push(i);}vector<int> res;for (auto x : a) {if (map_x_y.count(x) == 0) {res.emplace_back(-1);} else {res.emplace_back(map_x_y[x]);}}return res;}
};

python3代码如下,

class Solution:def nextGreaterElement(self, a: List[int], b: List[int]) -> List[int]:n = len(b)stk = []map_x_y = collections.defaultdict(int) for i in range(n-1,-1,-1):while len(stk) > 0 and b[stk[-1]] <= b[i]:del stk[-1]if len(stk) > 0:map_x_y[b[i]] = b[stk[-1]]stk.append(i)res = []for x in a:if x in map_x_y:res.append(map_x_y[x])else:res.append(-1)return res 

题目3:503. 下一个更大元素 II

解题思路:数组中下一个更大的数。单调栈模型。

C++代码如下,

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> a;for (auto x : nums) a.emplace_back(x);for (auto x : nums) a.emplace_back(x);int n = a.size();stack<int> stk;vector<int> res(n, -1);for (int i = n-1; i >= 0; --i) {while (!stk.empty() && a[stk.top()] <= a[i]) {stk.pop();}if (!stk.empty()) {res[i] = a[stk.top()];}stk.push(i);}res.erase(res.begin()+n/2, res.end());return res;}
};

python3代码如下,

class Solution:def nextGreaterElements(self, a: List[int]) -> List[int]:a += a n = len(a)stk = []res = [-1] * n for i in range(n-1,-1,-1):while len(stk) > 0 and a[stk[-1]] <= a[i]:del stk[-1]if len(stk) > 0:res[i] = a[stk[-1]]stk.append(i)return res[0:n//2]

题目4:42. 接雨水

解题思路:每一列的雨水高度,取决于,该列左侧最高的柱子和该列右侧最高的柱子,两者高度的较小值。

C++代码如下,

class Solution {
public:int trap(vector<int>& a) {int n = a.size();vector<int> lmax(n, a[0]);for (int i = 1; i < n; ++i) {lmax[i] = max(a[i], lmax[i-1]);}vector<int> rmax(n, a.back());for (int i = n-2; i >= 0; --i) {rmax[i] = max(a[i], rmax[i+1]);}int res = 0;for (int i = 0; i < n; ++i) {res += min(lmax[i], rmax[i]) - a[i];}return res;}
};

python3代码如下,

class Solution:def trap(self, a: List[int]) -> int:n = len(a)lmax = [a[0]] * nfor i in range(1,n):lmax[i] = max(a[i], lmax[i-1])rmax = [a[-1]] * n for i in range(n-2,-1,-1):rmax[i] = max(a[i], rmax[i+1])res = 0for i in range(n):res += min(lmax[i],rmax[i])-a[i]return res

题目5:84. 柱状图中最大的矩形

解题思路:

C++代码如下,


python3代码如下,


3 参考

代码随想录官网

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com