# Stack topic

# [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

## Question: (Easy)
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
## Solution: C++

class Solution {
public:
    bool isValid(string s) {
        vector<char> stack;
        int s_size = s.length();
        map<char, char> mapping;
        mapping[')'] = '(';
        mapping[']'] = '[';
        mapping['}'] = '{';
        for(int i=0; i<s_size; i++){
            if(s[i]==')'||s[i]==']'||s[i]=='}'){
                if(stack.size()==0)
                    return false;
                char temp = stack.back();
                stack.pop_back();
                if(temp!=mapping[s[i]]){
                    return false;
                }
            }
            else{
                stack.push_back(s[i]);
            }
        }
        return (stack.size()==0)?true:false;
    }
};

## Notes:
1. Using vector to create a stack which used to save brackets.
2. When getting "}" or "]" or ")", pop the first element in stack.

---

# [155. Min Stack](https://leetcode.com/problems/min-stack/)

## Question: (Medium)
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
## Solution: C++

class MinStack {
public:
    vector<int> stack;
    vector<int> min_stack;
    MinStack() {
        
    }
    
    void push(int val) {
        if(stack.size()==0&&min_stack.size()==0){
            stack.push_back(val);
            min_stack.push_back(val);
        }
        else{
            stack.push_back(val);
            if(val<=min_stack.back()){
                min_stack.push_back(val);
            }
        }
    }
    
    void pop() {
        int temp = stack.back();
        stack.pop_back();
        if(temp==min_stack.back())
            min_stack.pop_back();
    }
    
    int top() {
        int top_val = stack.back();
        return top_val;
    }
    
    int getMin() {
        int minima = min_stack.back();
        return minima;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

## Notes:
1. Using **two stacks** to solve this problem.
2. Variable **stack** is used to store element like original stack.
3. Variable **min_stack** is used to store element which smaller than **min_stack**'s top value.
---

# 739. Daily Temperatures
## Question: (Medium)
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

## Solution: C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        vector<pair<int, int>> stack;
        // <index, value>
        for(int i=0; i<temperatures.size(); i++){
            if(stack.size()==0){
                stack.push_back(pair<int, int>(i, temperatures[i]));
            }
            else if(temperatures[i]<=(stack.back().second)){
                stack.push_back(pair<int, int>(i, temperatures[i]));
            }
            else if(temperatures[i]>(stack.back().second)){
                while(temperatures[i]>(stack.back().second)){
                    pair<int, int> temp = stack.back();
                    stack.pop_back();
                    ans[temp.first] = i-temp.first;
                    //cout<<temp.first<<" "<<i-temp.first<<endl;
                    if(stack.size()==0)
                        break;
                }
                stack.push_back(pair<int, int>(i, temperatures[i]));
            }
        }
        return ans;
    }
};

## Notes:
1. 建立一個stack結構，裡面存{index, value}。
2. 若temperatures[i] > stack.top()，則計算答案，i-th所需要的天數為i-stack.top().index。
3. 若temperatures[i] < stack.top()，則放入stack中。
---

# 150. Evaluate Reverse Polish Notation
## Question: (Medium)
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
## Solution: C++

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> stack;
        for(int i=0; i<tokens.size(); i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int temp2 = stack.back(); stack.pop_back();
                int temp = stack.back(); stack.pop_back();
                if(tokens[i] == "+"){
                    stack.push_back(temp+temp2);
                }
                else if(tokens[i] == "-"){
                    stack.push_back(temp-temp2);
                }
                else if(tokens[i] == "*"){
                    stack.push_back(temp*temp2);
                }
                else if(tokens[i] == "/"){
                    cout<<temp<<" "<<temp2<<" "<<temp/temp2<<endl;
                    stack.push_back(temp/temp2);
                }
            }
            else{ // for number
                cout<<stoi(tokens[i])<<endl;
                stack.push_back(stoi(tokens[i]));
            }
        }
        return stack.back();
    }
};

## Notes:
1. 有修過資料結構的話，應該都會這題
2. input是postfix格式的數學式子，用stack就可以計算出數值
3. 遇到數字就放入stack，若是operator(EX: + - * /)則從stack中取出2個element來做相對應的運算。
4. 第3步完成後，將計算出來的數值重新放入stack中。

---

# 853. Car Fleet
## Question: (Medium)
There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.
Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.
Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
## Solution: C++

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, int>> data;
        vector<double> time_stack;
        for(int i=0; i<position.size(); i++){
            data.push_back(pair<int, int>(position[i], speed[i]));
        }
        sort(data.begin(), data.end());
        for(int i=data.size()-1; i>=0; i--){
            double t = double((target-data[i].first)/(0.0+data[i].second));
            if(time_stack.size()==0)
                time_stack.push_back(t);
            else if(t>time_stack.back()){
                time_stack.push_back(t);
            }
        }
        return time_stack.size();
    }
};

## Notes:
1. 這題其實不需要想太複雜，只需要計算每個position到target所花費的時間(t)
2. 需要先對position做排序
3. 若A的t < B的t，就代表A一定會追上B。
4. 用stack存t，若t>stack.pop()，則放進stack (stack越下面的t越小，代表離target只需要花費少亮時間，所以他們可以原地不動，等待後面的車子，這就是用stack的原因)
5. 若t<stack.pop()，則不用放進stack

---

# 22. Generate Parentheses
## Question: (Medium)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:

Input: n = 1
Output: ["()"]

## Solutions: C++

class Solution {
public:
    vector<string> ans;
    void backtracking(string str, int open_count, int close_count, int n){
        if(open_count==n&&close_count==n){
            ans.push_back(str);
            return;
        }
        if(close_count==open_count){
            backtracking(str+"(", open_count+1, close_count, n);
        }
        if(close_count<open_count){
            if(open_count<n){
                backtracking(str+"(", open_count+1, close_count, n);
            }
            if(close_count<n){
                cout<<"hi "<<str<<endl;
                backtracking(str+")", open_count, close_count+1, n);
            }
        }
    }
    vector<string> generateParenthesis(int n) {
        backtracking("(", 1, 0, n);  
        return ans;
    }
};

## Notes:
這題就是給定一個input n，輸出其括號的排列組合(n個左括弧、n個右括弧)，且需要符合規定。
1. 用recursive的方式來完成
2. 在iterative的時候，左括號的數量>右括號的數量(因為反之一定不符合規定)
3. 接著就是簡單的if-else來判斷要加左括號，還是右括號。 (括號的數量必須小於n)
4. 若左括號跟右括號的數量為n，則代表找出組合了且符合規則

---
# 735. Asteroid Collision
## Question (Medium)
We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
## Solution (C++)

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> stack;
        for(int i=0; i<asteroids.size(); i++){
            if(stack.size()==0 || stack.back()<0){
                stack.push_back(asteroids[i]);
                continue;
            }
            while(true){
                cout<<stack.back()<<" "<<asteroids[i]<<endl;
                if((stack.back()>0 && asteroids[i]>0) || stack.back()<0){
                    stack.push_back(asteroids[i]);
                    break;
                }
                else if(stack.back()>0 && asteroids[i]<0){
                    if(abs(stack.back()) == abs(asteroids[i])){
                        stack.pop_back();
                        break;
                    }
                    else if(abs(stack.back()) > abs(asteroids[i])){
                        break;
                    }
                    else if(abs(stack.back()) < abs(asteroids[i])){
                        stack.pop_back();
                        if(stack.size()==0){
                            stack.push_back(asteroids[i]);
                            break;
                        }
                    }
                }

            }
        }
        return stack;
    }
};

## Notes:
* 用stack模擬行星碰撞即可
* 若最前面的行星是negative number，則直接放入stack中，因為不影響結果
* 若有碰撞發生，碰撞完後，需要再次檢查是否會與stack的top element再次發生碰撞。
---

# 2462. Total Cost to Hire K Workers
## Question (Medium)
You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

You will run k sessions and hire exactly one worker in each session.
In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].
In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.
If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
A worker can only be chosen once.
Return the total cost to hire exactly k workers.

Example 1:

Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.
Example 2:

Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.
## Solution (C++)

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        long long sum = 0;
        if(costs.size() == 1)
            return costs[0];
        int left_index = candidates-1;
        int right_index = costs.size()-candidates;
        priority_queue<int, vector<int>, greater<int>> left;            
        priority_queue<int, vector<int>, greater<int>> right;
        for(int i=0; i<=left_index; i++)
            left.push(costs[i]);
        if(left_index>=right_index)
            right_index = left_index+1;
        for(int i=right_index; i<costs.size(); i++)
            right.push(costs[i]);
        right.push(INT_MAX);
        left.push(INT_MAX);
        while(k--){
            if(left.top() < right.top() || left.top() == right.top()){
                sum+=left.top();
                left.pop();
                if(left_index+1 < right_index){
                    left_index++;
                    left.push(costs[left_index]);
                }
            }
            else if(left.top() > right.top()){
                sum+=right.top();
                right.pop();
                if(right_index-1>left_index){
                    right_index--;
                    right.push(costs[right_index]);
                }
            }
        }
        return sum;
    }
};

## Notes
* 創建兩個priority_queue，分別存左邊的candidates和右邊的candidates
* 若是最小的是在左邊的priority_queue，則pop出來，並且將costs[left_index+1]放入priority_queue
* 要注意edge case，left_index和right_index是有可能交集的。
---