（京东笔试）大佬第一题合唱队形

leetcode 768

int main() {     int n;     cin >> n;     vector<pair<int, int>> vi;     int i = 0, num;     while (i < n) {         cin >> num;         vi.push_back({ num, i });         i++;     }     sort(vi.begin(), vi.end(), [](const pair<int, int> &a, const pair<int, int> &b) {return a.first < b.first;});     int cnt = 0;     for (i = 0; i < n; i++) {         int tmp = vi.at(i).second;         if (tmp == i) { cnt++; continue;}         int j = i;         for (; j <= tmp; j++) {             tmp = max(tmp, vi.at(j).second);         }         cnt++;         i = j - 1;         }     cout << cnt << endl;     return 0; }

说个思路吧

第一题思路：先对数组排序，然后遍历一遍，统计每个数字在排序树组中第一次出现的位置（数组元素重复时这个下标会出错），遍历结果记录在index数组中，最后对index数组一遍遍历，用maxIndex保存当前最大的index，maxIndex表示当前数组中应当分为一组的最大下标，在i<maxIndex的过程中需要不断更新maxIndex，直到maxIndex等于遍历的位置i时，说明一个合法的子数组遍历完成。 例子： nums[] = {2,1,6,3,5,4},得到的index[] = {1, 0, 5, 2, 4, 3},第一个合法子数组应该到i=1的位置，第二个合法数组应该到i=5的位置。 AC只有64%，因为这种做法无法处理有重复数字的情况。 import java.util.ArrayList; import java.util.Scanner; public class JD1 { /*  * 2 2 3 1 1 4  * */     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         int n = scanner.nextInt();         ArrayList<Integer> nums = new ArrayList<>();         int[] origin = new int[n];         int[] index = new int[n];         for(int i=0;i<n;i++) {             int cur = scanner.nextInt();             origin[i] = cur;             nums.add(cur);         }         nums.sort((o1,o2)->o1-o2);         for(int i=0;i<n;i++) {             index[i] = nums.indexOf(origin[i]);         }         int maxIndex = 0;         int count = 0;         for(int i=0;i<n;i++) {             //if(maxIndex==index[i]) maxIndex+=1;             maxIndex = Math.max(maxIndex, index[i]);             if(maxIndex == i) count++;         }         System.out.println(count);     } }