- Prepare
- Data Structures
- Stacks
- Maximum Element
- Discussions
Maximum Element
Maximum Element
+ 56 comments Posting a Java solution, that has O(1) access to get the maximum value in the stack.
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int max = Integer.MIN_VALUE; Stack<StackNode> stack = new Stack<StackNode>(); while (n > 0) { int choice = sc.nextInt(); if(choice == 1) { int val = sc.nextInt(); max = Math.max(val, max); stack.add(new StackNode(val, max)); } else if(choice == 2) { if(!stack.isEmpty()) stack.pop(); // reset max if(stack.isEmpty()) max = Integer.MIN_VALUE; else max = stack.peek().curMax; } else if(choice == 3) { if(!stack.isEmpty()) { System.out.println(stack.peek().curMax); } } n--; } sc.close(); } private static class StackNode { int val; int curMax; public StackNode(int val, int curMax) { this.val = val; this.curMax = curMax; } public String toString() { return val + " [" + curMax + "]"; } }
+ 23 comments Solution using C++, the slowest time is 0.02s
int main() { std::stack<int> st; int n, x; scanf("%d", &n); for (int i = 0; i < n; i++) { int q; scanf("%d", &q); switch (q) { case 1: scanf("%d", &x); if (st.empty()) { st.push(x); } else { st.push(max(x, st.top())); } break; case 2: if (!st.empty()) { st.pop(); } break; case 3: printf("%d\n", st.top()); break; default: break; } } return 0; }
+ 18 comments Short and simple without custom stack implemenatation.
#python 3 items = [0] for i in range(int(input())): nums = list(map(int, input().split())) if nums[0] == 1: items.append(max(nums[1], items[-1])) elif nums[0] == 2: items.pop() else: print(items[-1])
+ 9 comments [Solution Spoilers]
It seems the editorial solution and several mentioned here are needlessly complex. We do not need to maintain two stacks. Instead, we can use a single stack of integers: For query (1), instead of pushing element X, we simply push max(x, stack.peek()). For query (2), simply pop an element. For query (3), print stack.peek().
In a nutshell, we don't care that X is at the top of the stack if there is an element Y > X further down in the stack, so why not just push Y?
+ 4 comments For this particular question, we can simply keep a stack of the maximum values only at every level and ignore the original data of the stack.
Java O(1) solution :
public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int queries = in.nextInt(); Stack<Integer> maxValues = new Stack<Integer>(); while(queries-- > 0) { switch(in.nextInt()) { case 1 : int item = in.nextInt(); if (!maxValues.isEmpty()) { item = item > maxValues.peek() ? item : maxValues.peek(); } maxValues.push(item); break; case 2 : maxValues.pop(); break; case 3 : System.out.println(maxValues.peek()); break; } } in.close(); } }
Sort 1358 Discussions, By:
Please Login in order to post a comment