憨批min栈数据结构与算法

Abstract

【憨批min栈】讨论了min栈变形题, 获取栈中第二小的数, 的思路

Min栈常规思路
双栈stackA, stackB
变形题求第二小的数
case1 第一小和第二小可以重复
本质上还是单调栈, push时, 针对min栈, 如果小于等于栈顶就加入
pop时, 如果和min栈顶相等, 则min栈pop

public void push(int x) { stack.push(x); if (min.isEmpty() || x <= min.peek()) { min.push(x); } }public void pop() { int top = stack.pop(); if (top == min.peek()) { min.pop(); } }

case2 不允许重复
min栈为严格单调栈, 关注的问题是弹栈的时机 -> 假设min栈顶为top, 当stack栈中最后一个top弹出时, min栈弹出.
需要Map记录count值

public void push(int x) { stack.push(x); if (min.isEmpty() || x < min.peek()) { // 单调性 min.push(x); map.put(x, 1); } else if (x == min.peek()) { // 不push, 但需要count map.put(x, map.get(x) + 1); } else { // > min的情况, 不处理 } }public void pop() { int val = stack.pop(); if (min.peek() == val) { int count = map.get(val); count--; map.put(val, count); if (count == 0) min.pop(); } }