剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

https://www.nowcoder.com/exam/oj/ta?tpId=13

题目

思路 & 代码

栈结构的push、pop、top操作都是O(1)、O(1)、O(1)，但是min函数做不到，于是想到在push的时候就将最小值记录下来，由于栈先进后出的特殊性，我们可以构造一个单调栈，保证栈内元素都是递增的，栈顶元素就是当前最小的元素。

创建两个栈：

• stack1用来记录实际添加的数据

• stack2一个用来记录当前栈中的最小值，是一个单调栈

  • 当stack1为空，说明目前栈中没有数据，则添加进来的数据就是当前所有数据的最小值，stack2中添加该数据

  • 当stack1不为空，说明栈中有数据，用stack2栈顶元素与即将添加的数据node进行比较

    • 如果栈顶元素值大于node，则说明当前node是栈中最小值，stack2中添加node数据

    • 如果栈顶元素值小于node，则说明stack2栈顶元素的值是栈中最小值，则再次添加stack2的栈顶元素到stack2中

import java.util.*;
import java.util.Stack;

public class Solution {

    //记录正常的进栈、出栈数据
    private Stack<Integer> stack1 = new Stack<>();

    //构造一个单调栈
    private Stack<Integer> stack2 = new Stack<>();


    public void push(int node) {
        stack1.push(node);
        //如果stack2为空，则直接把node加进去
        if (stack2.isEmpty()) {
            stack2.push(node);
        } else {
            //stack2不为空，将node与stack2栈顶元素相比较
            if (node > stack2.peek()) {
                //node较大，则重复添加stack2的栈顶元素
                stack2.push(stack2.peek());
            } else {
                //node较小，添加node
                stack2.push(node);
            }
        }
    }

    public void pop() {
        stack1.pop();
        stack2.pop();
    }

    public int top() {
        return stack1.peek();
    }

    public int min() {
        return stack2.peek();
    }
}