当前位置： 首页 > article >正文

【数据结构与算法 | 灵神题单 | 栈基础篇】力扣155, 1472, 1381

article 2024/11/15 17:22:41

1. 力扣155：最小栈

1.1 题目：

设计一个支持 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
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

1.2 思路：

可以用优先队列的思想（堆）解决，也可以用单调栈。思路都是让每次找到最小的元素的时间复杂度为O(1)。优先队列每次弹出最小值，单调栈每次也弹出最小值。

1.3 题解1: 单调栈

class MinStack {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    public MinStack() {
        stack1 = new LinkedList<>();
        // stack2是单调栈
        stack2 = new LinkedList<>();
    }
    
    public void push(int val) {
        // 单调栈的执行逻辑，每次让小的元素靠近栈顶
        // 添加元素的时候，类似于插入排序的思想。
        if(stack2.isEmpty()){
            stack2.push(val);
        }else{
            if(stack2.peek() > val){
                stack2.push(val);
            }else{
                Deque<Integer> stack3 = new LinkedList<>();
                while(!stack2.isEmpty() && stack2.peek() < val){
                    stack3.push(stack2.pop());
                }
                stack2.push(val);
                while(!stack3.isEmpty()){
                    stack2.push(stack3.pop());
                }
            }
        }
        stack1.push(val);
    }
    
    public void pop() {
        stack2.remove(stack1.pop());
    }
    
    public int top() {
        return stack1.peek();
    }
    // 直接取单调栈栈顶元素。
    public int getMin() {
        return stack2.peek();
    }
}

1.4 题解2：堆

class MinStack {
    Deque<Integer> deque;
    PriorityQueue<Integer> pq;
    public MinStack() {
        deque = new LinkedList<>();
        pq = new PriorityQueue<>();
    }
    
    public void push(int val) {
        deque.push(val);
        pq.offer(val);
    }
    
    public void pop() {
        int val = deque.pop();
        pq.remove(val);
    }
    
    public int top() {
        return deque.peek();
    }
    
    public int getMin() {
        int val = pq.poll();
        pq.offer(val);
        return val;
    }
}

2. 力扣1472：设计浏览器历史记录

2.1 题目：

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

  • BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
  • void visit(string url) 从当前页跳转访问 url 对应的页面  。执行此操作会把浏览历史前进的记录全部删除。
  • string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
  • string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

示例：

输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

提示：

  • 1 <= homepage.length <= 20
  • 1 <= url.length <= 20
  • 1 <= steps <= 100
  • homepage 和 url 都只包含 '.' 或者小写英文字母。
  • 最多调用 5000 次 visit， back 和 forward 函数。

2.2 思路：

设计题，编程语言翻译题目意思。

2.3 题解：

class BrowserHistory {
    
    List<String> list = new LinkedList<>();
    // i是指向当前页面的指针
    int i;
    public BrowserHistory(String homepage) {
        list.add(homepage);
        i = 0;
    }
    //如果当前页面就是最新页面，那么就新增页面
    // 否则将当前页面的前面的历史页面都删除，再新增页面
    public void visit(String url) {
        if(i == list.size() - 1){
            i++;
            list.add(url);
        }else{
            for(int j = list.size() - 1; j > i; j--){
                list.remove(j);
            }
            list.add(url);
            i++;
        }
    }
    // 回退失败的话就回退到第一个页面
    public String back(int steps) {
        i = i - steps;
        // 回退失败
        if(i < 0){
            i = 0;
            return list.get(0);
        }
        return list.get(i);
    }
    // 前进失败的话就前进到最新页面
    public String forward(int steps) {
        i += steps;
        if(i >= list.size()){
            i = list.size()-1;;
            return list.get(list.size()-1);
        }
        return list.get(i);
    }
}

3. 力扣1381：设计一个支持增量操作的栈

3.1 题目：

请你设计一个支持对其元素进行增量操作的栈。

实现自定义栈类 CustomStack ：

  • CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量。
  • void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
  • int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
  • void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。

示例：

输入：
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出：
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释：
CustomStack stk = new CustomStack(3); // 栈是空的 []
stk.push(1);                          // 栈变为 [1]
stk.push(2);                          // 栈变为 [1, 2]
stk.pop();                            // 返回 2 --> 返回栈顶值 2，栈变为 [1]
stk.push(2);                          // 栈变为 [1, 2]
stk.push(3);                          // 栈变为 [1, 2, 3]
stk.push(4);                          // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
stk.increment(5, 100);                // 栈变为 [101, 102, 103]
stk.increment(2, 100);                // 栈变为 [201, 202, 103]
stk.pop();                            // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202]
stk.pop();                            // 返回 202 --> 返回栈顶值 202，栈变为 [201]
stk.pop();                            // 返回 201 --> 返回栈顶值 201，栈变为 []
stk.pop();                            // 返回 -1 --> 栈为空，返回 -1

提示：

  • 1 <= maxSize, x, k <= 1000
  • 0 <= val <= 100
  • 每种方法 increment，push 以及 pop 分别最多调用 1000 次

3.2 思路：

设计题，翻译题目意思。

3.3 题解：

class CustomStack {
    Deque<Integer> stack = new LinkedList<>();
    int maxsize;
    //记录栈中的最大个数
    int size;
    public CustomStack(int maxSize) {
        maxsize = maxSize;
    }
    
    public void push(int x) {
        if(size < maxsize){
            stack.push(x);
            size++;
        }
    }
    
    public int pop() {
        if(size == 0){
            return -1;
        }
        size--;
        return stack.pop();
    }
    
    public void increment(int k, int val) {
        // 栈中元素总数小于k
        if(size <= k){
            int n = size;
            while(n-- > 0){
                // 从栈顶删除元素，然后加入到新的栈
                stack.push(stack.pollLast() + val);
            }
        }else{
            int n = k;
            Deque<Integer> stack1 = new LinkedList<>();
            while(n-- > 0){
                stack1.push(stack.pollLast() + val);
            }
            while(!stack.isEmpty()){
                stack1.push(stack.pollLast());
            }
            stack = stack1;

        }
        
    }
}


http://www.kler.cn/a/316079.html

相关文章：

  • Docker 的安装与使用
  • CCI3.0-HQ：用于预训练大型语言模型的高质量大规模中文数据集
  • MySQL —— MySQL逻辑架构与查询过程
  • 【大数据学习 | HBASE高级】storeFile文件的合并
  • JavaSecLab靶场搭建
  • SHA-256哈希函数
  • 微信小程序03-页面交互
  • vue3中使用iframe不成功的问题
  • 逻辑回归 和 支持向量机（SVM）比较
  • 【深入理解SpringCloud微服务】了解微服务的熔断、限流、降级，手写实现一个微服务熔断限流器
  • 【spring】引入 Jackson 依赖 对java对象序列号和反序列化
  • 基于单片机的智能温控风扇系统的设计
  • C语言实现冒泡排序
  • 在泰国旅游不会口语怎么办？求推荐翻译软件！！！
  • 网安新声 | 黎巴嫩BP机爆炸事件带来的安全新挑战与反思
  • 计算机毕业设计选题推荐-基于python+Django的全屋家具定制服务平台
  • Vue3实现类ChatGPT聊天式流式输出(vue-sse实现)
  • torch.embedding 报错 IndexError: index out of range in self
  • 数据结构之二叉树遍历
  • 【Linux系统编程】第二十一弹---进程的地址空间
  • 《概率论与数理统计》学渣笔记
  • uni-app功能 1. 实现点击置顶，滚动吸顶2.swiper一个轮播显示一个半内容且实现无缝滚动3.穿透修改uni-ui的样式
  • 美团测开OC！
  • 【论文串烧】多媒体推荐中的模态平衡学习 | 音视频语音识别中丢失导致的模态偏差对丢失视频帧鲁棒性的影响
  • erlang学习:Linux常用命令2
  • Github 2024-09-23 开源项目周报 Top15