> For the complete documentation index, see [llms.txt](https://syjohnson11.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://syjohnson11.gitbook.io/leetcode/8_data_structure/stack.md).

# Stack

## Java里尽量避免使用Stack class

* Stack class in Java uses synchronized methods since it is a subclass of Vector.
* A more complete and consistent set of LIFO stack operations is provided by the [`Deque`](https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html) interface and its implementations, which should be used in preference to this class. For example:

```
   Deque<Integer> stack = new ArrayDeque<Integer>();
```

## [Minimum Remove to Make Valid Parentheses](https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses)

* Stack + Set solution, 2 pass
* first pass
  * Stack to store index of pendingLeft
  * Set to store index of unpaired right bracket
  * move element from stack to set&#x20;
* then second pass:&#x20;
  * if set.contains(curIdx), then skip it/don't append it
* O(N) Time , O(N) space

```
public String minRemoveToMakeValid(String s) {
        int len = s.length();
        Stack<Integer> pendingLeft = new Stack<>();
        Set<Integer> unpairedright = new HashSet<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                pendingLeft.add(i);
            } else if (c == ')') {
                if (pendingLeft.isEmpty()) {
                    unpairedright.add(i);
                } else {
                    pendingLeft.pop();
                }
            }
        }
        while (!pendingLeft.isEmpty()) {
            unpairedright.add(pendingLeft.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            if (unpairedright.contains(i)) continue;
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
```

* 这题还有O(1) space solution, 不用Stack, Set
* 需要记录两个变量，pendingRight和unpairedLeft
* 先scan 一遍记录pendingRight cnt
* 然后再scan, 每次遇到一个left bracket, 则unpairedLeft++
* 比较tricky, 感觉面试时应该不要求优化到O(1)吧

```
public String minRemoveToMakeValid(String s) {
        int len = s.length();
        int pendingRight = 0;
        for (int i = 0; i < len; i++){
            if (s.charAt(i) == ')') pendingRight++;
        }
        StringBuilder sb = new StringBuilder();
        int unpairedLeft = 0;
        for (int i = 0;i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                if (unpairedLeft == pendingRight) continue; // no more pendingRight to be paired with current left
                unpairedLeft++;
            } else if (c == ')') {
                //try to pair with unpairedLeft
                pendingRight--;
                if (unpairedLeft == 0) continue; //no more unpairedLeft remaining, so need to skip current right
                unpairedLeft--;
            } 
            sb.append(c);
        }
        return sb.toString();
    }
```

##