vector<vector<string>> res;
/* 输入棋盘边⻓ n，返回所有合法的放置 */ vector<vector<string>> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。 vector<string> board(n, string(n, '.')); backtrack(board, 0);
return res;
}
// 路径:board 中小于 row 的那些行都已经成功放置了皇后 // 选择列表:第 row 行的所有列都是放置皇后的选择
// 结束条件:row 超过 board 的最后一行
void backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return; }
int n = board[row].size();
for (int col = 0; col < n; col++) {
// 排除不合法选择
if (!isValid(board, row, col))
continue; // 做选择
board[row][col] = 'Q';
// 进入下一行决策 backtrack(board, row + 1); // 撤销选择
board[row][col] = '.';

}
}
/* 是否可以在 board[row][col] 放置皇后? */
bool isValid(vector<string>& board, int row, int col) {
int n = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i < n; i++) {
    if (board[i][col] == 'Q')
        return false;
}
// 检查右上方是否有皇后互相冲突 for (int i = row - 1, j = col i >= 0 && j < n; i--,
+ 1; j++) {
    if (board[i][j] == 'Q')
        return false;
}
// 检查左上方是否有皇后互相冲突 for (int i = row - 1, j = col
- 1;
i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q')
            return false;
}
    return true;
}

int left_bound(int[] nums, int target)
{
  if (nums.length == 0) return -1;
  int left = 0;
  int right = nums.length; // 注意
  while (left < right) { // 注意
    int mid = (left + right) / 2;
    if (nums[mid] == target) {
            right = mid;
    } else if (nums[mid] < target) {
            left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid; // 注意 }
    }
  }
    return left;
}

int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; // 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2; if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1; }
}
// 检查出界情况
if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

int right_bound(int[] nums, int target) { if (nums.length == 0) return -1;
int left = 0, right = nums.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
right = mid; }
}
return left - 1; // 注意 }

if (nums[mid] == target) {
    left = mid + 1;
    当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left ，使得区间不断向右收缩，达到锁定右侧边界的目的。

int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) {
    int mid = left + (right - left) / 2; if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
    right = mid - 1;
    } else if (nums[mid] == target) {
    // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
    }
    // 这里改为检查 right 越界的情况，⻅下图
    if (right < 0 || nums[right] != target)
    return -1; return right;
    }

// base case,  state will changed "0" -> "1" for given char at 0
  dp[0][pattern.charAt(0)]=1;
  int shaldow=0;
  for (int i = 1; i < n; i++) {
      // to traver each char
      for (int c = 0; c < 256; c++) {
          if(pattern.charAt(i)==c){
              dp[i][c]=i+1;    //[!!!!111] Not = dp[i][c]+1;, should be i+1
          }else{
              dp[i][c]=dp[shaldow][c];
          }
      }
      shaldow=dp[shaldow][pattern.charAt(i)];  // ONLY start from "0" to check with prefix and save time
  }

public int maxProfit(int[] prices) {
    if(prices==null || prices.length<0)
        return 0;
    int n=prices.length;
    int profitNoholding=0,profitHolding=Integer.MIN_VALUE; // initially no transactions, the holding position will only be invalid
    for(int i=0;i<n;i++){
        int temp = profitNoholding;
        profitNoholding=Math.max(profitNoholding, profitHolding+prices[i]);
        profitHolding = Math.max(profitHolding, temp-prices[i]);
    }

    return profitNoholding;
}


public int maxProfit_best(int[] prices) {
    int total=0;
    // the philosophy is : add to total if current price is greater than previous one
    for(int i=1;i<prices.length;i++){
        if(prices[i]>prices[i-1]){
            total+=prices[i]-prices[i-1];
        }
    }
    return total;
}
}

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        if(nums==null) return nums;
        // for next greater , monotonic stack
        Stack<Integer> stack = new Stack();
        int n=nums.length;
        int[] rtn=new int[n];
        // looped, so use "%n" + 2n for loop processing
        for(int i=2*n-1;i>=0;i--){
            // to strip off unqualified element, aka. to keep monotonic stak
            while(!stack.isEmpty() && stack.peek()<=nums[i%n]){ //[!!!!] be careful of bug, it should be "<=", rather than "<", becaust the question is "greater than", and it will add current element to stack, so if "=", it should be populate out as well
                stack.pop();
            }
            rtn[i%n]=stack.isEmpty()?-1:stack.peek();
            stack.push(nums[i%n]);
        }
    return rtn;
    }
}

ListNode reverse(ListNode head) {
if (head.next == null) 
    return head; 
ListNode last = reverse(head.next); 
head.next.next = head;
head.next = null;
return last;
}