力扣hot100-->栈/单调栈

news/2024/11/26 2:26:11/

栈/单调栈

1. 20. 有效的括号

简单

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

有效字符串需满足:

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

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[ ]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([ ])"

输出:true

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

// 定义一个名为Solution的类,用于解决括号有效性问题。
class Solution {
public:
    // 函数isValid用于检查输入的字符串s是否是有效的括号序列。
    bool isValid(string s) {
        // 定义一个字符栈st,用于存放预期的闭括号。
        stack<char> st;

        // 获取输入字符串s的长度。
        int n = s.size();

        // 遍历字符串s中的每个字符。
        for(int i{}; i < n; ++i) {
            // 如果当前字符是开括号'(',则将对应的闭括号')'推入栈中。
            if(s[i] == '(') {
                st.push(')');
            } else if(s[i] == '[') {
                // 如果当前字符是开括号'[',则将对应的闭括号']'推入栈中。
                st.push(']');
            } else if(s[i] == '{') {
                // 如果当前字符是开括号'{',则将对应的闭括号'}'推入栈中。
                st.push('}');
            } else {
                // 如果当前字符是闭括号,检查栈是否为空或者栈顶元素是否与当前闭括号匹配。
                // 如果栈为空,或者栈顶元素与当前闭括号不匹配,则说明括号序列无效,返回false。
                if(st.empty() || st.top() != s[i]) return false;

                // 如果栈顶元素与当前闭括号匹配,则弹出栈顶元素。
                st.pop();
            }
        }

        // 遍历结束后,如果栈为空,则说明所有开括号都找到了匹配的闭括号,返回true。
        // 如果栈不为空,则说明有未匹配的开括号,返回false。
        return st.empty();
    }
};

2. 155. 最小栈

中等

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

实现 MinStack 类:

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

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出:
[null,null,null,null,-3,null,0,-2]解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        // 如果s2为空或者val小于等于s2的栈顶元素,则将val压入s2
        if(s2.empty() || val <= s2.top()) s2.push(val);
        // 将val压入s1
        s1.push(val);
    }
    
    void pop() {
        // 如果两个栈都为空,则直接返回
        if(s1.empty() && s2.empty()) return;
        // 如果s1的栈顶元素等于s2的栈顶元素,则也需要从s2中弹出元素
        if(s1.top() == s2.top()) s2.pop();
        // 从s1中弹出元素
        s1.pop();
    }
    
    int top() {
        // 如果s1为空,则返回-1表示栈为空
        if(s1.empty()) return -1;
        // 返回s1的栈顶元素
        return s1.top();
    }
    
    int getMin() {
        // 如果s2为空,则返回-1表示栈为空
        if(s2.empty()) return -1;
        // 返回s2的栈顶元素,即当前栈中的最小值
        return s2.top();
    }
private:
    stack<int> s1;
    stack<int> s2;
};

解释:

 pop方法中,返回空(null)是因为pop操作本身不返回任何值,它只是移除栈顶元素。如果栈为空,那么就没有元素可以移除,所以返回空表示没有操作发生。

top方法:当s1为空时,意味着栈中没有任何元素,因此没有栈顶元素可以返回。在这种情况下,返回-1作为一个标志值,表示栈为空。这是因为-1通常不会是一个合法的栈元素值,所以可以用作一个错误标志。

getMin方法:同样,当s2为空时,意味着没有最小值可以返回(因为栈中没有任何元素)。因此,返回-1作为一个标志值,表示栈为空。

3. 394. 字符串解码

中等

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

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

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

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

示例 1:

输入:s = "3[a]2[bc]"
输出:"aaabcbc"

示例 2:

输入:s = "3[a2[c]]"
输出:"accaccacc"

示例 3:

输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"

示例 4:

输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"

提示:

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300] 

  class Solution {
public:
    string decodeString(string s) {
        string res = ""; // 用于构建最终的解码字符串
        stack<int> nums; // 用于存储数字,这些数字表示重复的次数
        stack<string> strs; // 用于存储字符串片段
        int num = 0; // 用于记录当前读取的数字
        int len = s.size(); // 字符串s的长度
        for(int i = 0; i < len; ++i) {
            if(s[i] >= '0' && s[i] <= '9') {
                // 如果当前字符是数字,则累加到num中
                num = num * 10 + s[i] - '0';
            } else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
                // 如果当前字符是字母,则添加到res中
                res = res + s[i];
            } else if(s[i] == '[') {
                // 如果遇到'[',则将之前的数字和字符串片段压栈
                nums.push(num);
                num = 0;
                strs.push(res);
                res = "";
            } else {
                // 如果遇到']',则进行解码操作
                int times = nums.top();
                nums.pop();
                for(int j = 0; j < times; ++j)
                    strs.top() += res;
                res = strs.top();
                strs.pop();
            }
        }
        return res; // 返回解码后的字符串
    }
};

4.  739. 每日温度

中等

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

示例 1:

输入: temperatures= [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size(); // 获取温度数组的长度
        vector<int> result(n, 0); // 初始化结果数组,所有元素都设置为0
        stack<int> s; // 创建一个栈,用于存储索引

        // 遍历每一天的温度
        for (int i = 0; i < n; i++) {
            // 当栈不为空,且当前温度大于栈顶元素对应的温度时
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                // 取出栈顶元素,即之前存储的索引
                int index = s.top();
                // 计算当前天与之前存储的天之间的天数差,并存储在结果数组中
                result[index] = i - index;
                // 从栈中移除栈顶元素
                s.pop();
            }
            // 将当前天的索引压入栈中
            s.push(i);
        }
        // 返回结果数组
        return result;
    }
};


http://www.ppmy.cn/news/1549962.html

相关文章

nature communications论文 解读

题目《Transfer learning with graph neural networks for improved molecular property prediction in the multi-fidelity setting》 这篇文章主要讨论了如何在多保真数据环境&#xff08;multi-fidelity setting&#xff09;下&#xff0c;利用图神经网络&#xff08;GNNs&…

社团管理新体验:SpringBoot技术

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了社团管理系统的开发全过程。通过分析社团管理系统管理的不足&#xff0c;创建了一个计算机管理社团管理系统的方案。文章介绍了社团管理系统的系统分析部分&…

【Zookeeper】二、主从应用(master-worker架构)

以一张具有代表性的架构风格展开本篇论述 一般在这种架构中&#xff0c;主节点所负责的工作主要有 跟踪从节点状态分配任务到从节点&#xff0c;并跟踪任务的有效性&#xff08;任务是否正常执行完成&#xff09; 此时&#xff0c;我们需要关注三个问题 主节点崩溃 如果主节…

tcpdump抓取流量包详解

tcpdump 是 Linux 下强大的网络抓包工具&#xff0c;广泛用于网络诊断和分析。以下是对 tcpdump 的详细讲解&#xff0c;包括安装、使用方法和常见示例。 1. 基本概念 tcpdump 用于捕获和分析网络数据包&#xff0c;可以过滤并显示传输中的数据&#xff0c;支持协议、端口等多…

【JAVA】Java基础—面向对象编程:常用API与数据结构—集合框架(List、Set、Map等)

Java集合框架是Java编程语言中一个强大的工具集&#xff0c;它提供了数据结构的实现和操作方法&#xff0c;用于存储和处理对象。Java集合框架的核心接口包括List、Set和Map&#xff0c;它们为开发者提供了灵活而高效的数据管理方式。在日常开发中&#xff0c;集合框架的使用无…

微服务系列概览

分布式和微服务的区别是什么&#xff1f; 分布式是把一个集中式系统拆分成多个系统&#xff0c;每一个系统单独对外提供部分功能&#xff0c;整个分布式系统整体对外提供一整套服务。对于访问分布式系统的用户来说&#xff0c;感知上就像访问一台计算机一样。 而分布式架构的…

网络安全 - DOS

1.1.1 摘要 最近网络安全成了一个焦点&#xff0c;除了国内明文密码的安全事件&#xff0c;还有一件事是影响比较大的——Hash Collision DoS&#xff08;通过Hash碰撞进行的拒绝式服务攻击&#xff09;&#xff0c;有恶意的人会通过这个安全漏洞让你的服务器运行巨慢无比&…

[译]Elasticsearch Sequence ID实现思路及用途

原文地址:https://www.elastic.co/blog/elasticsearch-sequence-ids-6-0 如果 几年前&#xff0c;在Elastic&#xff0c;我们问自己一个"如果"问题&#xff0c;我们知道这将带来有趣的见解&#xff1a; "如果我们在Elasticsearch中对索引操作进行全面排序会怎样…