[leetcode] validate stack sequences

임택·2021년 2월 27일
0

알고리즘

목록 보기
41/63

problem

code

push -> peek:
check if pop element is equal
if yes -> pop, continue
if no -> push
break if
pop index is equal to length of pushed aray and
stack is not empty

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length == 0) return true;

        
        Stack<Integer> stack = new Stack<>();

        int pushIdx = 0;
        int popIdx = 0;

      	// loop until pushIdx < pushed.length
      	// stack is not empty 
      	// why? need to check popped bebore escaping loop
        while (pushIdx < pushed.length || !stack.isEmpty()) {
            
          	// compare peek and popped[current popped index]
          	// when stack is not empty
            if (!stack.isEmpty()) {
                int peek = stack.peek();
                if (peek == popped[popIdx]) {
                    stack.pop();
                    popIdx++;
                    continue;
                }
            }
            
            // when pushIdx == length of pushed
            // and stack is not empty
            // this means that sequences of pushed and popped differs
            // so break; or return false;
            if (pushed.length == pushIdx && !stack.isEmpty()) 
                break;
          
            stack.push(pushed[pushIdx]);
            pushIdx++;                

        }
        
        return stack.isEmpty();
        
    }
}

Time: O(N)
Space: O(N), stack size

leetcode solution

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int N = pushed.length;
        Stack<Integer> stack = new Stack();

        int j = 0;
        for (int x: pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        return j == N;
    }
}
  • what I need to consider, looping an array which must be iterated until the end. In this case, the pushed array must be iterated fully.
  • While iterating the pushed, iterating popped if and only if stack is not empty and a peek of stack is equal to popped[j]

from leetcode

A greedy solution is one where we always go for the immediately available option (for example, if you're finding the shortest route to a store, a greedy approach would be to always pick the smaller road when you're at a junction, and hope their sum will be the global minimum as well). But there are cases where greedy approaches are valid and make sense. Like in this case, if the element we just pushed matches the first element to pop, we know we should pop it immediately (greedy) and not later, because once it's pushed, it won't be pushed again unless it's popped, so we must pop.

Greedy choice refers to making decision based upon the locally available information and never changing it in future,

profile
캬-!

0개의 댓글