leetcode 困难题 871. Minimum Number of Refueling Stops 最低加油次数-内存100

Problem: 871. Minimum Number of Refueling Stops 最低加油次数

解题过程

内存100%，状态数组标记是否被使用，每次从当前能到达的最远的地方，期间所有的加油站选择油最多的站点，不停循环直到可以到达目的地

Code

using pr = pair<int, int>; class Solution { public: int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) { int n = stations.size(); vector<bool> status(n, false); int num = 0; while(true) { if(startFuel >= target) return num; int mx = INT_MIN, ind; for(int i = 0; i < n; i++) { if(status[i] == false && stations[i][0] <= startFuel) { if(mx < stations[i][1]) { mx = stations[i][1]; ind = i; } } } if(mx == INT_MIN) return -1; startFuel = startFuel + mx; status[ind] = true; num++; } return -1; } };