链接​​​​​​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); stackint 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[j1], 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); } };