首页 > 代码库 > 算法题——数组内有序对的最大距离

算法题——数组内有序对的最大距离

2024-07-17 23:15:35   215人阅读

题目：给定一个数组A，对于下标i < j，有A[i] < A[j]，求j - i 的最大值。

 

思路：先正序遍历一次，利用一个辅助数组，记录每个元素的左边子数组中最小值的下标；然后倒序遍历，维持两个指针，初始都指向最后一个元素，通过移动两个指针，找出最大距离。

 

代码：

 1 #include <iostream> 2 #include <vector> 3 using namespace std; 4  5 int maxDist(int num[], int n) 6 { 7     if(n < 2) 8         return 0; 9 10     vector<int> left_min_pos(n, 0);11     int cur_min_pos = 0;12     int max_dist = 0;13 14     for(int i = 1; i < n; ++i)15     {16         if(num[i] < num[cur_min_pos])17         {18             left_min_pos[i] = i;19             cur_min_pos = i;20         }21         else22         {23             left_min_pos[i] = cur_min_pos;24         }25     }26 27     for(int i = n - 1, j = n - 1; i >= 0; )　　//i < j28     {29         i = left_min_pos[i];30         31         if(num[j] >= num[i])    //找到一个有序对，或是同一个元素32         {33             if(j - i > max_dist) 34             {35                 max_dist = j - i;36             }37             --i;            //对于当前的i来说，j已是最远的，所以固定住j，i往左走，找到更大的j-i38         }39         else40         {41             --j;            //不是有序对，对于j来说，上一个i已是最远的，固定住i，j往左走42         }43     }44 45     return max_dist;46 }47 48 int main()49 {50     const int n = 5;51     int num[n] = {3, 6, 4, 1, 2};52 53     cout << maxDist(num, n) << endl;54 55     return 0;56 }

 


联系
我们