关于java:LeetCode155最小栈

50次阅读

共计 1356 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：设计一个反对 push，pop，top 操作，并能在常数工夫内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。

pop() —— 删除栈顶的元素。

top() —— 获取栈顶元素。

getMin() —— 检索栈中的最小元素。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：双栈

利用 2 个栈，一个栈 data 存储数据，一个栈 minVal 存储最小值，具体方法逻辑：

push()：将 val 值放到 data 的栈顶，判断 val 值是否小于等于 minVal 的栈顶元素，如果是，则将 val 值也放到 minVal 的栈顶；

pop()：将 data 的栈顶元素取出，判断如果取出的元素等于 minVal 的栈顶元素，则将 minVal 的栈顶元素也取出；

top()：查看 data 的栈顶元素；

getMin()：查看 minVal 的栈顶元素。

import java.util.Stack;

public class LeetCode_155 {public static void main(String[] args) {MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());   // 返回 -3.
        minStack.pop();
        System.out.println(minStack.top());      // 返回 0.
        System.out.println(minStack.getMin());   // 返回 -2.
    }
}

class MinStack {
    private Stack<Integer> data;
    private Stack<Integer> minVal;

    /**
     * initialize your data structure here.
     */
    public MinStack() {data = new Stack<>();
        minVal = new Stack<>();}

    public void push(int val) {data.push(val);
        if (minVal.isEmpty()) {minVal.push(val);
        } else if (val <= minVal.peek()) {minVal.push(val);
        }
    }

    public void pop() {if (data.isEmpty()) {throw new RuntimeException("stack is empty.");
        }
        int popVal = data.pop();
        if (popVal == minVal.peek()) {minVal.pop();
        }
    }

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

    public int getMin() {if (minVal.isEmpty()) {throw new RuntimeException("stack is empty.");
        }
        return minVal.peek();}
}