力扣1562.查找大小为M的最新分组
力扣1562.查找大小为M的最新分组
-
用link数组记录每一段区间的左右端点
- 当且仅当i点为端点时，link[i]有意义
-
int lint[100001] = {0};class Solution {public:int findLatestStep(vector<int>& arr, int m) {int cnt = 0;memset(lint, -1, sizeof(lint));int anw = -1;for(int i = 0; i < arr.size(); i++) {int pos = arr[i] - 1;//自己单独一个区间lint[pos] = pos;int L = pos, R = pos;//左边有1 说明当前i为右端点if(0 < pos && lint[pos-1] != -1) {//区间长度 = 右端点 - 左端点 + 1//如果是m 说明m即将消失if(pos-1 - lint[pos-1] + 1 == m) {cnt--;}//仍然是原来的左端点L = lint[pos-1];}//右边有1 说明当前i为左端点if(pos+1 < arr.size() && lint[pos+1] != -1) {if(lint[pos+1] - (pos+1) + 1 == m) {cnt--;}R = lint[pos+1];}lint[L] = R;lint[R] = L;//新区间是m长度if(R-L+1 == m) {cnt++;}//有m的区间 更新答案if(cnt > 0) {anw = i+1;}}return anw;}};