<p>Given an integer array <code>nums</code>, return <code>true</code><em> if there exists a triple of indices </em><code>(i, j, k)</code><em> such that </em><code>i &lt; j &lt; k</code><em> and </em><code>nums[i] &lt; nums[j] &lt; nums[k]</code>. If no such indices exists, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> true
<strong>Explanation:</strong> Any triplet where i &lt; j &lt; k is valid.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,4,3,2,1]
<strong>Output:</strong> false
<strong>Explanation:</strong> No triplet exists.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,5,0,4,6]
<strong>Output:</strong> true
<strong>Explanation:</strong> The triplet (3, 4, 5) is valid because nums[3] == 0 &lt; nums[4] == 4 &lt; nums[5] == 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Could you implement a solution that runs in <code>O(n)</code> time complexity and <code>O(1)</code> space complexity?
class Solution {
public:
	bool increasingTriplet(vector<int>& nums) {
		if (nums.size() < 3) return false;
		unordered_map<int, bool> T;
		for (auto s : nums) {
			T[s] = true;
		}
		if (T.size() < 3) return false;
		for (int i = 0; i < nums.size(); i++) {
			//跳过降序区间
			int u = i + 1;
			for (; u < nums.size(); u++) {
				if (nums[u - 1] < nums[u])
					break;
			}
			u--;
			if (u <= nums.size() - 3) {
				i = u;
			}
			else break;
			for (int j = i + 1; j < nums.size(); j++) {
				while (j < nums.size() && nums[j] <= nums[i]) {
					j++;
				}
				if (j == nums.size()) break;
				for (int k = j + 1; i < nums.size(); k++) {
					while (k < nums.size() && nums[k] <= nums[j]) {
						k++;
					}
					if (k == nums.size()) break;
					if (nums[i] < nums[j] && nums[j] < nums[k]) return true;
				}
			}
		}
		return false;
	}
};
116000