/*
LeetCode 739. Daily Temperatures

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]
 

Constraints:

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100


Brute force (show you know it, but say it's too slow)
→ For each i, scan j = i+1 to n-1, find first j where temperatures[j] > temperatures[i]
→ O(n²) → TLE on n=10⁵

Optimal approach: Monotonic decreasing stack (stores indices)

Maintain a stack of indices in decreasing order of temperatures (from bottom to top).
When we find a temperature warmer than the top of the stack → that day solves multiple
previous waiting days → pop them all and calculate distances.

================================================
index:  0  1  2  3  4  5  6  7
 temp: 73,74,75,71,69,72,76,73
------------------------------
index  temp  result[top()] = days
                           = index - top()
-----  ---   -------------------------------
0      73                                 push 0
1      74    result[0] = 1-0 = 1   pop 0
                                          push 1
2      75    result[1] = 2-1 = 1   pop 1
                                          push 2
3      71                                 push 3
4      69                                 push 4
5      72    result[4] = 5-4 = 1   pop 4
             result[3] = 5-3 = 2   pop 3
                                          push 5
6      76    result[5] = 6-5 = 1   pop 5
             result[2] = 6-2 = 4   pop 2
                                          push 6
7      73                                 push 7

        0 1 2 3 4 5 6 7
result: 1 1 4 2 1 1 0 0

================================================
temps: 73 74 75
i=0
                                     push 0
i=1
  top()=0 days=i-top()=1 result[0]=1 pop 0
                                     push 1
i=2
  top()=1 days=i-top()=1 result[1]=1 pop 1
                                     push 2
  
result: 1 1 0
================================================
temps: 75 74 73 76
i=0
  push 0
i=1
  push 1
i=2
  push 2
i=3
  top()=2 days=i-top()=1 result[2]=1 pop 2
  top()=1 days=i-top()=2 result[1]=2 pop 1
  top()=0 days=i-top()=3 result[0]=3 pop 0
  push 3

restul
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

void print(const string& label, vector<int>& v);

class Solution {
public:
/*
1. Iterate over the everyday temperature of the given array arr[] using the current index.
2. If the stack is empty, push the current index to the stack.
3. If the stack is not empty then do the following:

      If the temperature at the current index is lesser than the temperature of the index at top of
      the stack, push the current index.

      If the temperature at the current index is greater than the temperature of the index at top of
      the stack, then update the no of days to wait for warmer temperature as:

              current index – index at top of the stack
              Pop the stack once the number of days has been updated in the output list.
              lastly push the current index
              
4. Repeat the above steps for all the indices in the stack that are
      lesser than the temperature at the current index.

*/
    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {

        int n = temperatures.size();
        vector<int> result(n, 0);   // default 0 = no warmer day
        stack<int> st;              // stores indices of temps decreasing

        for (int i = 0; i < n; ++i)
        {
            cout << format("i={}\n", i);
            while (!st.empty() && temperatures[i] > temperatures[st.top()])
            {
                int days = i - st.top();
                result[st.top()] = days;
                cout << format("  top()={} days=i-top()={} result[{}]={} pop {}\n", st.top(), days, st.top(), days, st.top());
                st.pop();
            }
            st.push(i); cout << format("  push {}\n", i);
        }
        return result;
    }
};

int main(void)
{
    vector<tuple<vector<int>, vector<int>>> testCases = {
        // input
        //   output
        { {73,74,75,71,69,72,76,73},
          { 1, 1, 4, 2, 1, 1, 0, 0}},
        // { {73,74,75,76,77},
        //   { 1, 1, 1, 1, 0}},
        // { {73,72,71,70,69,74},
        //   { 6, 5, 4, 3, 2, 1, 0}},
        // { {73,72,71,70},
        //   { 0,0,0,0}},
        { {73,74,75},
          {  1,1,0}},
        { {75,74,73,76},
          {  3,2,1,0}},

    };

    Solution s;

    for (const auto& tc: testCases)
    {
        vector<int> input = get<0>(tc);
        print("input", input);        
        vector<int> result = s.dailyTemperatures(input);

        string in; for(auto& i: input) in += to_string(i) + " ";
        string expected; for(auto& i: get<1>(tc)) expected += to_string(i) + " ";
        string res; for(auto& i: result) res += to_string(i) + " ";

        cout << format("temps: {}\n expected: {}\n   result: {}\n", in, expected, res);
        EXPECT_EQ(result, get<1>(tc));
        cout << setw(30) << setfill('-') << '-' << endl;
    }
}

void print(const string& label, vector<int>& v)
{
    string s(label + ": [");
    for (auto& i: v) s += to_string(i) + ",";
    s = s.substr(0, s.size() - 1);    
    s += "] ";
    cout << s << endl;
}