[LeetCode]Daily Temperatures

对于处在i的元素nums[i]，这道题要我们找在i右边的，比nums[i]大的并且最靠近i的元素。Brute force的做法，是对于每一个元素nums[i]我们向右边找符合要求的数，时间复杂度是O(n^2)。显然我们有很多可以优化的地方，如果我们从右向左扫，在nums[i]处，那么在寻找nums[i + 1]对应的数的时候所排除的所有数，在寻找nums[i]对应的数的时候就不需要考虑了，因为：

• 如果nums[i] >= nums[i - 1]，我们排除掉的所有数都是小于等于nums[i - 1]，自然也小于等于nums[i]的，不是我们要找的数
• 如果nums[i] < nums[i - 1]，那么nums[i]对应要找的数就是nums[i - 1]

所以我们如果从右向左扫描，维护一个从左向右的递增序列。对于nums[i]，我们pop所有栈顶小于等于nums[i]的数。这些数就是我们上面所说的不需要考虑的数，如果此时栈顶还有元素，那就是我们要找的nums[i]对应的数，否则，i的右边不存在比nums[i]更大的数。这道题要求距离，我们存index即可。时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	vector<int> dailyTemperatures(vector<int>& temperatures) {
	int len = temperatures.size();
	stack<int> st;
	vector<int> res;
	for (int i = len - 1; i >= 0; --i)
	{
	while (st.size() && temperatures[st.top()] <= temperatures[i])st.pop();
	res.push_back(st.empty() ? 0 : st.top() - i);
	st.push(i);
	}
	reverse(res.begin(), res.end());
	return res;
	}
	};

view raw Daily Temperatures.cpp hosted with ❤ by GitHub

另一种方法，因为我们直接利用我们要return的数组next，next记录了对于每个nums[i]其右边大于nums[i]最近的数的距离。那么对于nums[i]来说，有两种情况：

• nums[i] < nums[i + 1]，next[i] = 1
• nums[i] >= nums[i + 1]，我们找到nums[i + 1 + next[i + 1]]，这个是满足条件的对应nums[i + 1]的数，所有在(i + 1, i + 1 + next[i + 1])都可以根据我们之前的分析排除。继续用nums[i + 1 + next[i + 1]]和nums[i]比较，直到我们找到满足条件的数或者发现找不到

这个做法的时间复杂度显然不是O(n^2)，因为对于nums[i]，如果我们要一路回溯到最右端，那么[i + 1, len - 1]一定是一个递增序列，并且nums[i + 1] <= nums[i], nums[i] >= nums[len - 1]。那么这个递增序列，每一个数要向右找一位，假设[i, len - 1]长度为m，所以每一次yamotized time为(m - 1 + m - 1) / m = O(1)。那么对于nums来说，我们可以把其切分成不同的这样的序列，这样总的时间复杂度依然是O(n)。空间复杂度，不考虑return数组要开的空间，我们没有用额外的空间。代码如下：

	class Solution {
	public:
	vector<int> nextGreaterElements(vector<int>& nums) {
	int len = nums.size(), maxIdx = -1;
	vector<int> next(len);
	stack<int> st;
	for(int i = 0; i < 2 * len; ++i)
	{
	int idx = (len - i + len) % len;
	while(st.size() && st.top() <= nums[idx])st.pop();
	next[idx] = st.empty()? -1: st.top();
	st.push(nums[idx]);
	}
	return next;
	}
	};

view raw Daily Temperatures_2.cpp hosted with ❤ by GitHub