锐客网

  1. 首页 > it技术 > >

739.|739. Daily Temperatures（week7）

739. Daily Temperatures 题目描述 Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
解题思路 【739.|739. Daily Temperatures（week7）】简单的说，这道题需要我们找到某个数组元素后面的最早出现的元素。简单的思路就是：从这个点出发，找后面的所有点，是否有比它还要大的元素；如果出现了，就记录下二者下标的差值；若没有，则记录下0。这是一种可取的思路，假设平均在后面的第k个点才找到符合要求的值，那么这个算法的复杂度将会是O(N * K)。k的大小取决于数据，如果这是一个从大到小排列的序列，那么K = n/2。复杂度将会是O(n^2)的规模。而题目给出的数组大小会达到30000，很显然，这种方法是不可取的。

在上述的方法中，对每一个点，我们都遍历了太多不符合要求的点。最好的情况是，对于每一个点，我们只需要知道它自己的值以及第一个符合要求的值即可，那么我们要如何实现呢？考虑用一个栈结构来存储这个列表。对于每一个元素，我们在进栈之前，先判断栈顶元素是否比它要小，若比它要小，则栈顶元素最早出现的比它自身大的元素就是当前的元素，出栈并继续判断；若栈顶元素不比它小，则进栈。这样一来，每一个元素我们最多只会对它进行一次入栈和出栈的操作，这样一来，复杂度就会由O(N * K)下降到O(2n)。而付出的代价是，多维护了一个栈空间。
时间复杂度分析 对于每一个元素而言，最多只进行一次入栈和出栈的操作，复杂度为O(n)。
空间复杂度分析 能够存下n个元素的栈以及返回的结果，复杂度为O(n)。
源码

class Solution { public: vector dailyTemperatures(vector& T) { stack Tstack; map next; for (int i = 0; i < T.size(); ++i) { if (Tstack.empty()) { Tstack.push(i); } else { while (!Tstack.empty()) { int topIndex = Tstack.top(); if (T[i] > T[topIndex]) { Tstack.pop(); next[topIndex] = i - topIndex; } else { break; } } Tstack.push(i); } } while (!Tstack.empty()) { next[Tstack.top()] = 0; Tstack.pop(); } vector result; for (int i = 0; i < T.size(); ++i) { result.push_back(next[i]); } return result; } };

    推荐阅读


    上一篇：胃疼

    下一篇：10063