質問する

問題のソース

トラブルシューティングポリシー

最初は問題を説明しても毒があるかどうか分からなかった.
まず,インデックス伝達基準としての1つの砲口と基準の後に残るインデックスにおいて,基準より小さい値があれば降順変換のタイミングで砲口から離れるようにコードを記述する.

コード1

vector<int> solution(vector<int> prices){
	int l = prices.size();
	vector<int> answer(l, 0);
	for(int i = 0;i < l;i++){
		for(int j = i+1;j < l;j++){
			answer[i] += 1;
			if(prices[i] > prices[j]) break;
		}

	}
	return answer;
}

上記のコードは、現在のインデックスの位置から単純に開始し、次のインデックスから最後の秒数(informixj)まで保持した後、降順で変換した瞬間loopを追加するだけです.
時間複雑度O(n^2)のコード.

他者コード

実際、スタックを使って解凍できると思っていたのですが、久しぶりにスタック容器を使っていたので面倒だったのですが、TEKEを通過した後は、別の考えがなさそうでした.
スタックプール
Test Case
1, 2, 3, 2, 3
0, 1, 2, 3, 4
i = 0
s.push(0);
stack = 0
i = 1
prices[0] > prices[1] x
s.push(1);
stack = 1 0
i = 2
s.top = 1
price[1] > price[2]
s.push(2);
stack = 2 1 0
i = 3
s.top = 2
answer[2] = 3-2;
stack = 3 1 0
i = 4
s.top = 3
stack = 4 3 1 0
最後に
answer[4] = 5 - 4 - 1;
stack = 3 1 0
answer[3] = 5 - 3 - 1;
stack = 1 0
answer[1] = 5 - 1 - 1;
stack = 0
answer[0] = 5 - 0 - 1;
answer = [4, 3, 1, 1, 0]

#include<string>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;

vector<int> solution(vector<int> prices){
        vector<int> answer(prices.size());
        stack<int> s;
        int size = prices.size();
        for(int i = 0;i < size;i++){
                while(!s.empty() && prices[s.top()] > prices[i]) {
                        answer[s.top()] = i-s.top();
                        s.pop();
                }
                s.push(i);
        }
        while(!s.empty()){
                answer[s.top()] = size - s.top()-1;
                s.pop();
        }
        return answer;

}

要するに、増加したインデックスはすべてスタックに配置され、後で計算され、減少したインデックスは文の中でのみ検索され、while文の中で答えの値が事前に計算されます.