【leetcode100-069到073】【栈】五题合集

2024-01-28 04:04

本文主要是介绍【leetcode100-069到073】【栈】五题合集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【有效括号】

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

思路:

遇到左括号入栈,遇到右括号弹一个出来看是否匹配,全部走完看栈里是否还有没配对的左括号,如果以上步骤中任意时刻出问题,直接返回false,都没出问题则返回true。

class Solution {
public:bool isValid(string s) {vector<char> stk;for (int i = 0; i < s.size(); i++) {if (s[i] == '(' || s[i] == '{' || s[i] == '[') {stk.push_back(s[i]);}if (s[i] == ')') {if (stk.empty()||stk.back() != '(' )return false;stk.pop_back();}if (s[i] == '}') {if (stk.empty()||stk.back() != '{')return false;stk.pop_back();}if (s[i] == ']') {if (stk.empty()||stk.back() != '[')return false;stk.pop_back();}}return stk.empty();}
};

【最小栈】

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

思路:

对于栈中任意元素,在它出栈前,比它更靠近栈底的元素是不可能发生变化的,那么我们使用一个辅助栈,记录当前元素及其下方所有元素中的最小值即可。

class MinStack {
public:stack<int> stk;stack<int> stk_min;MinStack() { stk_min.push(INT_MAX); }void push(int val) {stk.push(val);if (val < stk_min.top())stk_min.push(val);elsestk_min.push(stk_min.top());}void pop() {if (!stk.empty()) {stk.pop();stk_min.pop();}}int top() { return stk.top(); }int getMin() { return stk_min.top(); }
};

【字符串解码】

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

思路:

我们可以把每一对括号想象成一个递归函数的调用和返回,遇到左括号=一个新的调用,因此要把当前的“现场”保存下来,然后先去进行内层函数的计算,遇到右括号=内层函数返回,返回的时候要把之前保存的“现场”恢复,继续进行外层函数的计算。我们用一个栈来模拟现场的保存和恢复。

class Solution {
public:string decodeString(string s) {stack<int> numStk;stack<string> strStk;int num = 0;string cur = "";for (int i = 0; i < s.size(); i++) {//数字if (s[i] >= '0' && s[i] <= '9') {num = num * 10 + (s[i] - '0');}//括号else if (s[i] == '[') {numStk.push(num);num = 0;strStk.push(cur);cur = "";} else if (s[i] == ']') {int n = numStk.top();numStk.pop();string temp = strStk.top();strStk.pop();for(int i=0;i<n;i++) {temp += cur;}cur = temp;}//字母else {cur += s[i];}}return cur;}
};

【每日温度】

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

【柱状图最大矩形】

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

思路:

第一题的思路就是第二题思路的一部分,就放在一起讲了。

对第一题来说,要找的是比自身大的,因此在遍历时,遇到小的先存起来,只有当前元素比栈顶下标元素大时,才开始弹出栈内下标,直到栈内没有比当前元素更大的数时停止,并把当前元素入栈。第一题做到这里就够了,因为对任意元素我们只需要考虑它后面的元素,而最后留在栈内的元素就是没有合法的后续元素的,标0就可以。

第二题的逻辑和第一题相同,只是评判条件和第一题相反,因为要找的是第一个小于当前元素的,找到它就找到了当前矩形的右边界,而栈内元素是递增的,左边界就是栈顶元素下面的元素(其实不一定,可能会有非严格递增的情况,也就是栈顶和它下面的元素一样大,但因为本题找的是最大值,这样做对结果不会有影响,所以就不单独拿出来讨论了)。然后对最后剩余元素的处理不太一样,他们延伸出的矩形一直到数组边界都是合法的,所以我们把数组边界作为它的右边界来做计算,左边界的选取方法不变。

class Solution 
{
public:vector<int> dailyTemperatures(vector<int>& temperatures) {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n=temperatures.size();vector<int> st(n,0);vector<int> ans(n,0);int j=0;for(int i=0;i<n;i++){while((j > 0) && temperatures[st[j]] < temperatures[i]){ans[st[j]]=i-st[j];j--;}j++;st[j]=i;    }return ans;}
};
class Solution {
public:int largestRectangleArea(vector<int>& heights) {if (!heights.size())return 0;stack<int> stk;stk.push(-1);int maxArea = 0;int l = 0, r = 0, curHeight = 0, curArea = 0;for (int i = 0; i < heights.size(); i++) {//空栈或能延伸if (stk.top() == -1 || heights[i] >= heights[stk.top()]) {stk.push(i);continue;}//把能确定面积的都算了并退栈while (stk.top() != -1 && heights[i] < heights[stk.top()]) {curHeight = heights[stk.top()];stk.pop();curArea = (i - stk.top() - 1) * curHeight;maxArea = max(maxArea, curArea);}stk.push(i);}//处理还没能出栈的//还有while (stk.top() != -1) {curHeight = heights[stk.top()];stk.pop();curArea = (heights.size() - stk.top() - 1) * curHeight;maxArea = max(maxArea, curArea);}return maxArea;}
};

这篇关于【leetcode100-069到073】【栈】五题合集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/652423

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

EasyPlayer.js网页H5 Web js播放器能力合集

最近遇到一个需求,要求做一款播放器,发现能力上跟EasyPlayer.js基本一致,满足要求: 需求 功性能 分类 需求描述 功能 预览 分屏模式 单分屏(单屏/全屏) 多分屏(2*2) 多分屏(3*3) 多分屏(4*4) 播放控制 播放(单个或全部) 暂停(暂停时展示最后一帧画面) 停止(单个或全部) 声音控制(开关/音量调节) 主辅码流切换 辅助功能 屏

C++语法知识点合集:11.模板

文章目录 一、非类型模板参数1.非类型模板参数的基本形式2.指针作为非类型模板参数3.引用作为非类型模板参数4.非类型模板参数的限制和陷阱:5.几个问题 二、模板的特化1.概念2.函数模板特化3.类模板特化(1)全特化(2)偏特化(3)类模板特化应用示例 三、模板分离编译1.概念2.模板的分离编译 模版总结 一、非类型模板参数 模板参数分类类型形参与非类型形参 非类型模板

Linux性能分析工具合集

Linux性能分析工具合集 工具合集主要包含以下各种工具,对于了解Linux系统结构、网络结构、内核层次具有一定的帮助。 Linux Performance Observability ToolsLinux Static Performance ToolsLinux Performance Benchmark ToolsLinux Performance Tuning ToolsLinux

JVM合集

序言: 1.什么是JVM? JVM就是将javac编译后的.class字节码文件翻译为操作系统能执行的机器指令翻译过程: 前端编译:生成.class文件就是前端编译后端编译:通过jvm解释(或即时编译或AOT)执行.class文件时跨平台的,jvm并不是跨平台的通过javap进行反编译 2.java文件是怎么变成.class文件的? 属于前端编译 3..class文件解读 采用1

C语言程序与设计第四版课后习题 - 1~8章大合集

前言 本文章是一个大合集,按照课后习题的命名方式命名,方便寻找,只需要在目录上点相对应的题号即可在这里插入图片描述 第一章课后习题 1.1 编写一个C程序 题目概述: 请参照本章例题,编写一个C程序,输出一下信息: *****************************Very good!***************************** 代码实现: #define

《黑神话:悟空》专题合集MOD/修改器/壁纸/音乐/CG剧情

《黑神话:悟空》专题合集」 链接:https://pan.quark.cn/s/d67857f4e308 包含内容: 《黑神话:悟空》MOD合集 《黑神话:悟空》修改器(风灵月影) 《黑神话:悟空》壁纸合集 《黑神话:悟空》3小时CG完整剧情合集 4K120帧最高画质!国语 简中字幕 附:4K 结尾动画合集 ​​​国语 简中字幕 《黑神话:悟空》主题曲 《黑神话

【鼠鼠学AI代码合集#5】线性代数

在前面的例子中,我们已经讨论了标量的概念,并展示了如何使用代码对标量进行基本的算术运算。接下来,我将进一步说明该过程,并解释每一步的实现。 标量(Scalar)的基本操作 标量是只有一个元素的数值。它可以是整数、浮点数等。通过下面的 Python 代码,我们可以很容易地进行标量的加法、乘法、除法和指数运算。 代码实现: import torch# 定义两个标量x = torch.tens

diffusion model 合集

diffusion model 整理 DDPM: 前向一步到位,从数据集里的图片加噪声,根据随机到的 t t t 决定混合的比例,反向要慢慢迭代,DDPM是用了1000步迭代。模型的输入是带噪声图和 t,t 先生成embedding后,用通道和的方式加到每一层中间去: 训练过程是对每个样本分配一个随机的t,采样一个高斯噪声 ϵ \epsilon ϵ,然后根据 t 对图片和噪声进行混合,将加噪

【新东西】链接合集

1、RxJava。 基础介绍:http://www.jianshu.com/p/5e93c9101dc5 详细介绍:http://gank.io/post/560e15be2dca930e00da1083 方法介绍:https://zhuanlan.zhihu.com/p/21926591 2、Retrofit。网络请求框架,外包代码里用的这个。 简单介绍:http://blog.csd