力扣－每日温度

. - 力扣（LeetCode）

这是我的第一个思路 虽然可以得到正确答案 但是过于暴力 已经超出了时间限制 

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int>ans;for (int i = 0; i < temperatures.size(); ++i){int max = 0, cnt = 0;for (int j = i + 1; j < temperatures.size(); ++j){++cnt;if ( temperatures[j] > temperatures[i] ){max = cnt;break;}}ans.push_back( max );}return ans;}
};

随后 我发现这类题都有一个通发 这种数据有增有减 我们就可以采取极端假设法 假设全为增或者全为减 在这里 我才去的是全是减 将不满足条件的数先存放起来 然后就写

这是我的第一次修改 但是报错了 因为ans[i] = 0; 因为没有指定数组大小直接访问数组下标 导致数组越界了 经过查询 可以把那行代码修改为这个 动态分布内存  ans.push_back(0);

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> ans;stack<int> stk;for (int i = 0; i < temperatures.size(); ++i) { // 初始化顺序表全为0ans[i] = 0;}for (int i = 0; i < temperatures.size(); ++i) {while (stk.size() && temperatures[ stk.top() ] < temperatures[i]) {ans[ stk.top() ] = i - stk.top();stk.pop();}stk.push(i);}return ans;}

修改代码如下

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> ans;  //初始化ans大小为size, 数据全部为0stack<int> stk;for (int i = 0; i < temperatures.size(); ++i){ans.push_back(0);}for (int i = 0; i < temperatures.size(); ++i) {while (stk.size() && temperatures[ stk.top() ] < temperatures[i]) {ans[ stk.top() ] = i - stk.top();stk.pop();}stk.push(i);}return ans;}
};

但是这样子还是有点慢了 我们可以直接初始化数组大小以及数组的数据

像这样： vector<int> ans( temperatures.size(), 0);  //初始化ans大小为size, 数据全部为0

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> ans( temperatures.size(), 0);  //初始化ans大小为size, 数据全部为0stack<int> stk;for (int i = 0; i < temperatures.size(); ++i) {while (stk.size() && temperatures[ stk.top() ] < temperatures[i]) {ans[ stk.top() ] = i - stk.top();stk.pop();}stk.push(i);}return ans;}
};

然后就过了