301. Remove Invalid Parentheses 移除非法括号

[GH1995]

301. Remove Invalid Parentheses

Difficulty: Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

Solution

Language: C++

// #include "leetcode.h"
​
class MedianFinder {
 private:
  priority_queue<int> maxpq;  // 存放较小的一半数字
  priority_queue<int, vector<int>, greater<int>> minpq;  // 存放较大的一半数字
  // maxpq.top() <= minpq.top()
​
 public:
  /** initialize your data structure here. */
  MedianFinder() {}
​
  void addNum(int num) {
    maxpq.push(num);  // 从 maxpq 中移除最大元素并提供给 minpq
    minpq.push(maxpq.top());
    maxpq.pop();
​
    if (maxpq.size() <
        minpq.size()) {  // 如果 minpq 较大，则移除较小元素给 maxpq
      maxpq.push(minpq.top());
      minpq.pop();
    }
  }
​
  double findMedian() {
    if (minpq.size() == maxpq.size())
      return (minpq.top() + maxpq.top()) * 1.0 / 2;
    else
      return maxpq.top();
  }
};
​
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
​