每日温度

暴力求解法：

代码语言：javascript复制

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        vector<int> ret;
        ret.resize(T.size(),0);
        cout << ret.size() << endl;
        for (int i = 0; i < T.size(); i  )
        {
            for (int j = i 1; j < T.size(); j  )
            {
                if (T[j] > T[i])
                {
                    ret[i] = j - i;
                    break;
                }
            }
        }
        return ret;
    }
}; 

效率低，需要时间长

单调栈解决：

代码语言：javascript复制

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        stack<int> s;//存放的是下标
        vector<int> ret;
        ret.resize(T.size());
        for (int i = 0; i < T.size(); i  )
        {
            //当栈不为空且当前插入元素大小大于栈顶元素的时候，将栈顶元素出栈
            while (!s.empty()&&T[i]>T[s.top()])
            {
                ret[s.top()] = i - s.top();//通过下标之差可以求得里最近的较大者的距离
                s.pop();
            }
            s.push(i);
        }
        return ret;
    }
}; 

从后开始查找：

代码语言：javascript复制

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        vector<int> ret;
        ret.resize(T.size());
        for (int i = T.size() - 2; i >= 0; i--)
        {
            int j = i   1;
            while (j < T.size())
            {
                //后一个元素是否比前一个元素大，如果大，那么距离为坐标之差
                if (T[j] > T[i])
                {
                    ret[i] = j - i;//计算完当前ret[i]就可以跳出循环
                    break;
                }
                else if(ret[j]==0)//说明当前j元素后面没有比当前j指向元素更大的值
                {
                    break;
                }
                else 
                {
                    //如果后一个相邻的元素没有比当前i指向元素大，那么就需要找比后一个相邻元素大的最近位置，再次进行比较
                    j  = ret[j];
                }
            }
        }
        return ret;
    }
}; 

单调栈用法：判别是否需要使用单调栈，如果需要找到左边或者右边第一个比当前位置的数大或者小

效率

0 人点赞