HackerRank‐Stacks and Queuess - a920604a/leetcode GitHub Wiki

string isBalanced(string s) {
    stack<char> sta;
    for(char c:s){
        if(c=='(' || c=='[' || c=='{') sta.push(c);
        else{
            if(sta.empty()) return "NO";
            else if(sta.top() == '(' && c==')') sta.pop();
            else if(sta.top() == '[' && c==']') sta.pop();
            else if(sta.top() == '{' && c=='}') sta.pop();
            else return "NO";
        }
    }
    return sta.empty()?"YES":"NO";
}

class MyQueue {
    public:
        stack<int> stack_newest_on_top, stack_oldest_on_top;   
        void push(int x) {
            stack_newest_on_top.push(x);
        }

        void pop() {
            if (stack_oldest_on_top.empty()){
                while (!stack_newest_on_top.empty()){
                    stack_oldest_on_top.push(stack_newest_on_top.top());
                    stack_newest_on_top.pop();
                }
            }
            stack_oldest_on_top.pop();
        }

        int front() {
            if (stack_oldest_on_top.empty()){
                while (!stack_newest_on_top.empty()){
                    stack_oldest_on_top.push(stack_newest_on_top.top());
                    stack_newest_on_top.pop();
                }
            }
            return stack_oldest_on_top.top();
        }
};

long largestRectangle(vector<int> h) {
    long ret = 0;
    stack<int> sta;
    h.push_back(0);
    for(int i=0;i<h.size() ; ++i){
        while(!sta.empty() && h[sta.top()] >= h[i]){
            int t = sta.top(); sta.pop();
            if(!sta.empty()) ret = max( ret, (long)(i-sta.top()-1)*h[t]);
            else ret = max(ret, (long)i*h[t]);
        }
        sta.push(i);
    }
    return ret;
}

int minimumMoves(vector<string> grid, int startX, int startY, int goalX, int goalY) {
    int move = 0, n=grid.size();
    queue<vector<int>> q;
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    q.push({startX,startY});
    visited[startX][startY] = true;
    while(!q.empty()){
        int size = q.size();
        for(int k=0;k<size ; ++k){
            vector<int> cur = q.front();
            q.pop();
            if(cur[0] == goalX && cur[1] == goalY) return move;
            int x = cur[0], y=cur[1];
            vector<vector<int>> nei;
            for(int j=y;j<n;++j){
                if(grid[x][j]=='.') nei.push_back({x,j});
                else break;
            }
            for(int j=y-1;j>-1;j--)
            {
                if(grid[x][j]=='.') nei.push_back({x,j});
                else break;
            }
            for(int i=x;i<n;++i){
                if(grid[i][y]=='.') nei.push_back({i,y});
                else break;
            }
            for(int i=x-1;i>-1;--i){
                if(grid[i][y]=='.') nei.push_back({i,y});
                else break;
            }
            
            for(vector<int> n:nei){
                if(!visited[n[0]][n[1]]) {
                    q.push({n[0], n[1]});
                    visited[n[0]][n[1]] = true;
                }
            }
        }
        move++;
    }
    return move;
}