# 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();
    }
```

##


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/8_data_structure/stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.