##題目描述 定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊中所含最小元素的min函式（時間復雜度應為O（1））， 注意：保證測驗中不會當堆疊為空的時候，對堆疊呼叫pop()或者min()或者top()方法，
思路
不同步輔助堆疊，時間復雜度O(1)，空間復雜度O(n)，
基數堆疊，在存放資料的堆疊里存放val-min，min作為基數單獨用int變數存放，
基數堆疊時間復雜度O(1)，空間復雜度O(1)，致命缺陷是存放val-min導致可push資料的域值折半，
輔助堆疊代碼
import java.util.Stack;
public class Solution {
private Stack<Integer> stack = new Stack<Integer>();
private Stack<Integer> helper = new Stack<Integer>();
public void push(int node) {
stack.push(node);
if(helper.empty() || node <= helper.peek()) {
helper.push(node);
}
}
public void pop() {
if(!stack.empty()) {
if(stack.peek() == helper.peek()) {
helper.pop();
}
stack.pop();
}
}
public int top() {
if(!stack.empty()) {
return stack.peek();
}
throw new RuntimeException("堆疊空");
}
public int min() {
if(!stack.empty()) {
return helper.peek();
}
throw new RuntimeException("堆疊空");
}
}
基數堆疊代碼
import java.util.Stack;
public class Solution {
private Stack<Integer> stack = new Stack<Integer>();
private int _min;
private int _top;
public void push(int node) {
_top = node;
if(stack.empty()) {
_min = node;
}
stack.push(node - _min);
if(node < _min) {
_min = node;
}
}
public void pop() {
if(!stack.empty()) {
if(stack.peek() < 0) {
// stack.pop() == _top - 上一個_min
// 所以_min = _top - stack.pop();
_min -= stack.peek();
}
stack.pop();
if(!stack.empty()) {
// 連續最小值情況的考慮
_top = _min + stack.peek() > 0 ? stack.peek() : 0;
}
}
}
public int top() {
if(!stack.empty()) {
return _top;
}
throw new RuntimeException("堆疊空");
}
public int min() {
if(!stack.empty()) {
return _min;
}
throw new RuntimeException("堆疊空");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85159.html
標籤：其他
上一篇：順時針列印矩陣