婚庆网站名字,房地产信息管理系统软件,白云区网站开发公司电话,微信端微网站怎么做目录 1 专题说明2 训练 1 专题说明
本博客用来计算力扣上的单调栈题目、解题思路和代码。
单调栈题目记录#xff1a;
2232866美丽塔II 2 训练
题目1#xff1a;2866美丽塔II。
解题思路#xff1a;先计算出prefix[i]#xff0c;表示0~i满足递增情况下#xff0c;0~i… 目录 1 专题说明2 训练 1 专题说明
本博客用来计算力扣上的单调栈题目、解题思路和代码。
单调栈题目记录
2232866美丽塔II 2 训练
题目12866美丽塔II。
解题思路先计算出prefix[i]表示0~i满足递增情况下0~i上的元素之和最大值。然后计算出suffix[i]表示i~n-1满足递增情况下i~n-1上的元素之和最大值。那么以i为峰顶的美丽塔的元素之和的最大值为prefix[i] suffix[i] - nums[i]遍历i获得答案即可。
本质上还是可以归类为找到i左边并且nums[i]的元素值。
C代码如下
class Solution {
public:long long maximumSumOfHeights(vectorint maxHeights) {int n maxHeights.size();vectorlong long prefix(n, 0); //prefix[i]表示0~i是递增的情况下0~i的元素之和stackint stk;for (int i 0; i n; i) {while (!stk.empty() maxHeights[stk.top()] maxHeights[i]) {stk.pop();}if (stk.empty()) {prefix[i] (long long)(i 1) * maxHeights[i];} else {prefix[i] prefix[stk.top()] (long long)(i - stk.top()) * maxHeights[i];}stk.push(i);}while (!stk.empty()) {stk.pop();}vectorlong long suffix(n, 0); //suffix[i]表示i~n-1是递减的情况下i~n-1的元素之和for (int i n - 1; i 0; --i) {while (!stk.empty() maxHeights[stk.top()] maxHeights[i]) {stk.pop();}if (stk.empty()) {suffix[i] (long long)(n - i) * maxHeights[i];} else {suffix[i] suffix[stk.top()] (long long)(stk.top() - i) * maxHeights[i];}stk.push(i);}long long res 0;for (int i 0; i n; i) {res max(res, prefix[i] suffix[i] - maxHeights[i]);}return res;}
};python3代码如下
class Solution:def maximumSumOfHeights(self, maxHeights: List[int]) - int:n len(maxHeights)prefix [0 for i in range(n)] #0~i的递增数组的和的最大值stk []for i in range(n):while len(stk) and maxHeights[stk[-1]] maxHeights[i]:del stk[-1]if len(stk) 0:prefix[i] (i 1) * maxHeights[i]else:prefix[i] prefix[stk[-1]] (i - stk[-1]) * maxHeights[i]stk.append(i)stk.clear()suffix [0 for i in range(n)] #i~n-1的递减数组的和的最大值for i in range(n-1,-1,-1):while len(stk) and maxHeights[stk[-1]] maxHeights[i]:del stk[-1]if len(stk) 0:suffix[i] (n - i) * maxHeights[i]else:suffix[i] suffix[stk[-1]] (stk[-1] - i) * maxHeights[i]stk.append(i)res 0for i in range(n):#print(fi {i}, prefix[i] {prefix[i]}, suffix[i] {suffix[i]}.)res max(res, prefix[i] suffix[i] - maxHeights[i])return res题目2496下一个更大元素I。
解题思路直接找右边首次大于它的元素即可。
C代码如下
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {unordered_mapint,int mp; //mp[x]表示nums2中元素x的右边第一个比它大的元素stackint stk;for (int i nums2.size() - 1; i 0; --i) {while (!stk.empty() stk.top() nums2[i]) {stk.pop();}if (!stk.empty()) {mp[nums2[i]] stk.top();} else {mp[nums2[i]] -1;}stk.push(nums2[i]);}vectorint res;for (auto x : nums1) {res.emplace_back(mp[x]);}return res;}
};python3代码如下
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:n len(nums2)mp collections.defaultdict(int)stk []for i in range(n - 1, -1, -1):while len(stk) and stk[-1] nums2[i]:del stk[-1]if len(stk):mp[nums2[i]] stk[-1]else:mp[nums2[i]] -1stk.append(nums2[i])res []for x in nums1:res.append(mp[x])return res 题目3503下一个更大元素II。
解题思路环形问题扩展两倍原数组即可接下来就是找右侧首次大于它的元素。
C代码如下
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorint a(2 * n, 0);for (int i 0; i n; i) {a[i] a[i n] nums[i];}vectorint ans(2 * n, -1);stackint stk;for (int i 2 * n - 1; i 0; --i) {while (!stk.empty() stk.top() a[i]) {stk.pop();}if (!stk.empty()) {ans[i] stk.top();}stk.push(a[i]);}vectorint res(n, -1);for (int i 0; i n; i) {res[i] ans[i];}return res;}
};python3代码如下
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:n len(nums)a [-1 for i in range(2 * n)]for i in range(n):a[i] a[i n] nums[i]ans [-1 for i in range(2 * n)]stk []for i in range(2 * n - 1, -1, -1):while len(stk) and stk[-1] a[i]:del stk[-1]if len(stk):ans[i] stk[-1]stk.append(a[i])res [-1 for i in range(n)]for i in range(n):res[i] ans[i]return res 题目42454下一个更大元素IV。
解题思路比较难不懂先放一边。
题目5
