力扣－每日温度

. - 力扣（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) { // 初始化顺序表全为0
            ans[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, 数据全部为0
        stack<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, 数据全部为0
        stack<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;
    }
};

然后就过了

原文地址：https://blog.csdn.net/m0_63056769/article/details/143666609

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！