不算巧妙 从数据结构下手
包含min函数的栈
http://www.nowcoder.com/questionTerminal/4c776177d2c04c2494f2555c9fcc1e49
我刚开始是想使用LinkedList实现,牛客不让用java的集合,就没用了
想着不让用LinkedList,我就只能自定义一个List了
本着不麻烦够用就行的原则,写了个单链表。算法上没有有点 单纯的判断。
后来看题解,牛客可以用Stack集合,我晕,给个提示啊,能用什么不能用什么,让我大费周折!
private static class MyStack { private Node head; private int minValue; private static class Node { Node next; int value; Node(int value) { this.value = value; } Node(int value, Node next) { this.value = value; this.next = next; } } public void push(int node) { if (head == null) { head = new Node(node); minValue = node; } else { head = new Node(node, head); // 插入元素比最小值小 就替换最小值 minValue = minValue < node ? minValue : node; } } public void pop() { if (head == null) { return; } // 将头节点指向下个节点 int headValue = head.value; head = head.next; // 如果移除的数字和最小值相等 就要寻找最小值了 if (headValue == minValue) { Node n = head; // 没有节点了 重置最小值 if (n == null) { minValue = 0; return; } // 将头节点值赋给最小值 依次和后面比较 minValue = n.value; while (n != null) { minValue = minValue < n.value ? minValue : n.value; n = n.next; } } } public int top() { if (head != null) { return head.value; } return -1; } public int min() { return minValue; } }