O(n) solution using stack, it is very very strange that i submited the same code twice, first it took 22ms, second 9ms....why?


  • 0
    Z
    class Solution {
    public:
        int longestValidParentheses(string s) {
            stack<int> st;
            for (int i = 0; i < s.size(); ++i) {
                if (!st.empty() && s[i] == ')' && s[st.top()] == '(') st.pop();
                else st.push(i);
            }
            int res = 0;
            int pre = s.size();
            while (!st.empty()) {
                int t = pre - st.top() - 1;
                if (t > res) res = t;
                pre = st.top();
                st.pop();
            } 
            if (pre > res) res = pre;
            return res;
        }
    };

  • 0
    S

    @zhangwbnn correct me if I'm wrong, the online judge may not always have the same runtime everytime since you are sharing the resource on the machine with other ppl.


  • 0
    Z

    @superaye thanks for your explanation, I agree on you that leetcode OJ is not stable. Sometimes I submited the same code, it returned compile time limit exceeded.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.