企业官网建设流程全解析

链接：

​​​​​​670. 最大交换

题解：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

1.保持单调递减

2.如果当前元素比前面的大，则从当前位置到末尾找到，一个最大的元素，越后面越好

3.在前面的元素中，找到一个比他小的元素，越前面越好（因为前面的队列是单调的，可以用二分查找，找到第一个<target的位置）

4.交换这两个元素

class Solution { public: int maximumSwap(int num) { if (num <= 0) { return 0; } std::string str = to_string(num); stack<int> sta; int i = 0; for (i = 0; i < str.size(); ++i) { if (!sta.empty() && str[sta.top()] < str[i]) { break; } sta.push(i); } if (i == str.size()) { return num; } int max_val = i; for (int right = i; i < str.size(); ++i) { if (str[max_val] <= str[i]) { max_val = i; } } int left = i-1; while (!sta.empty() && str[max_val] > str[sta.top()]) { left = sta.top(); sta.pop(); } swap(str[left], str[max_val]); return atoi(str.c_str()); } };

class Solution { public: int maximumSwap(int num) { // 321578 if (num <= 0) { return num; } string str = to_string(num); // 按照单调递减查找，找到第一个非递减的位置 int i = 1; for (; i < str.size(); ++i) { if (str[i] > str[i-1]) { break; } } if (i == str.size()) { return num; } // [i,size) 之间找到一个最大的数字,倒着查询，这样有相同的是，在最后面的位置 int max_index = i; for (int j = i; j < str.size(); ++j) { if (str[j] >= str[max_index]) { max_index = j; } } // 前面都是降序的，找到第一个大于交换元素的位置停止 int j = i-1; for (j = i-1; j >= 0; --j) { //cout << "swap: " << str[j] << " " << str[max_index] << endl; if (str[j] >= str[max_index]) { break; } } // 置换最大元素 swap(str[j+1], str[max_index]); return atoi(str.c_str()); } };

class Solution { public: int maximumSwap(int num) { string str = to_string(num); string sta; int i = 0; for (i = 0; i < str.size(); ++i) { if (!sta.empty() && sta.back() < str[i]) { break; } sta += str[i]; } if (i == str.size()) { return stoi(str); } // 在 [i, n-1] 中找最大的数字（最右边的最大） int max_index = i; for (int j = i; j < str.size(); ++j) { if (str[max_index] <= str[j]) { max_index = j; } } // 在 [0, i-1] 中找最左边小于 str[max_index] 的位置 // 因为 [0, i-1] 非递减，用二分找"第一个 < target"的位置 int left = 0; int right = i - 1; while (left + 1 < right) { int mid = left + (right - left) / 2; if (str[mid] < str[max_index]) { right = mid; // ✅ mid 满足，往左找 } else { left = mid; // ✅ mid 不满足，往右找 } } // 循环结束时 left 和 right 相邻，优先检查 left（更靠左） int index = right; if (str[left] < str[max_index]) { index = left; } swap(str[index], str[max_index]); return stoi(str); } };