題目

?

示例

?

思路

• 離線查詢：
  • ?輸入的結(jié)果數(shù)組queries[]是無序的。如果我們按照輸入的queries[]本身的順序逐個(gè)查看，時(shí)間復(fù)雜度會(huì)比較高。 于是，我們將queries[]數(shù)組按照數(shù)值大小，由小到大逐個(gè)查詢，這種方法稱之為離線查詢。
• 位運(yùn)算：
  • ?離線查詢的時(shí)候，queries[]可以按照數(shù)值大小逐個(gè)查看，但最終返回的結(jié)果數(shù)組，是需要按照queries[]相同的順序輸出的，也就是說，queries[]數(shù)組的下標(biāo)信息不能被丟失。 此時(shí)，我們可以考慮，將每一個(gè)queries[x]放在一個(gè)long int數(shù)值的高32位，將下標(biāo)x放在這個(gè)long int數(shù)值的低32位。 由此，我們可以看出，這些新的long int數(shù)值，它們之間的相互大小關(guān)系，取決于高32位的數(shù)值，只有在高32位相等的時(shí)候，才需要比較低32位。如此，我們?cè)诒容^大小時(shí)，優(yōu)先看高32位，然后想要獲取其下標(biāo)信息時(shí)，直接取低32位。 類似的，我們?cè)谔幚磔斎氲膇ntervals[]數(shù)組時(shí)也類似處理。將每一個(gè)intervals[x]的左邊緣放在一個(gè)long int數(shù)值的高32位，右邊緣放在這個(gè)long int數(shù)值的低32位。這樣，這些long int數(shù)值，它們之間的相互大小關(guān)系，就取決于左邊緣的大小關(guān)系，而想要獲取右邊緣時(shí)，直接取低32位即可。
• 小根堆（優(yōu)先隊(duì)列）：
  • ????????我們要由小到大處理queries[]數(shù)組和intervals[]數(shù)組，可以考慮排序，也可以考慮小根堆，這里采用小根堆。

【具體實(shí)現(xiàn)】文章來源地址http://www.zghlxwxcb.cn/news/detail-588434.html

1. 將輸入的intervals[]數(shù)組，每一個(gè)intervals[x]的左邊緣放在一個(gè)long int數(shù)值的高32位，右邊緣放在這個(gè)long int數(shù)組的低32位，然后long int數(shù)值push入小根堆intervalsHeap。
2. 將輸入的queries[]數(shù)組，每一個(gè)queries[x]的數(shù)值放在一個(gè)long int數(shù)值的高32位，下標(biāo)x放在這個(gè)long int數(shù)值的低32位，然后long int數(shù)值push入小根堆queriesHeap。
3. 逐個(gè)從queriesHeap中pop出堆頂元素，這個(gè)堆頂元素的高32位就是上面第2步push入堆時(shí)，每一個(gè)queries[x]的數(shù)值，賦值給變量position，低32位就是下標(biāo)x。
   1. 3.1 從intervalsHeap中pop出所有左邊緣（高32位）小于等于position的區(qū)間。
   2. 3.2 上面3.1中pop出的每一個(gè)區(qū)間，把所有右邊緣（低32位）大于等于position的區(qū)間，都push入一個(gè)有效區(qū)間小根堆validHeap中。這個(gè)validHeap中，以區(qū)間的range為高32位，右邊緣為低32位，以保證堆頂?shù)膮^(qū)間range始終是最小的。
   3. 3.3 如果validHeap堆頂區(qū)間的右邊緣（低32位）小于當(dāng)前的position，則將其彈出。
   4. 3.4 經(jīng)過上面3.3的操作后，如果validHeap仍然非空，則說明存在包含這個(gè)position的區(qū)間，且validHeap的堆頂區(qū)間的range（高32位）就是題目要求的結(jié)果。

代碼

/* 幾個(gè)全局定義的說明。
  INVALID_VALUE:            無效值-1。小根堆中，根節(jié)點(diǎn)的父節(jié)點(diǎn)使用這個(gè)無效值。題目中結(jié)果數(shù)組里的無效值也是這個(gè)-1。
  FATHER_NODE(x):           小根堆中，每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。其中，根節(jié)點(diǎn)的父節(jié)點(diǎn)是無效值。
  LEFT_NODE(x):             小根堆中，每一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)。當(dāng)它大于等于堆size的時(shí)候無效。
  RIGHT_NODE(x):            小根堆中，每一個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)。當(dāng)它大于等于堆size的時(shí)候無效。
  MERGE_LONG(x, y):         兩個(gè)int數(shù)值合并成一個(gè)long int數(shù)值，其中x占據(jù)高32位，y占據(jù)低32位。
  GET_HIGHER32(x):          獲取一個(gè)long int數(shù)值的高32位值。
  GET_LOWER32(x):           獲取一個(gè)long int數(shù)值的低32位值。 */
#define INVALID_VALUE       -1
#define FATHER_NODE(x)      ((0 == (x)) ? INVALID_VALUE : ((x) - 1 >> 1))
#define LEFT_NODE(x)        (((x) << 1) + 1)
#define RIGHT_NODE(x)       (((x) << 1) + 2)
#define MERGE_LONG(x, y)    ((long int)(x) << 32 | (long int)(y))
#define GET_HIGHER32(x)     ((x) >> 32)
#define GET_LOWER32(x)      ((x) & 0xFFFFFFFF)

/* 小根堆的結(jié)構(gòu)定義，里面包括堆空間數(shù)組arr[]，和堆size。 */
typedef struct
{
    long int *arr;
    int arrSize;
}
HeapStruct;

static void heapPush(HeapStruct *heap, long int t);
static void heapPop(HeapStruct *heap);

/* 主函數(shù)的幾個(gè)變量說明：
  x:                循環(huán)下標(biāo)。
  position:         queries數(shù)組中的數(shù)值。因?yàn)檫@個(gè)數(shù)組會(huì)帶著下標(biāo)一起入堆，在出堆時(shí)，把它的實(shí)際數(shù)值取出到這個(gè)position。
  range:            題目中定義的一個(gè)左閉右閉區(qū)間的大小，等于“右邊緣 - 左邊緣 + 1”。
  t:                long int臨時(shí)數(shù)值。
  arr1,arr2,arr3:   幾個(gè)小根堆中要用到的堆空間數(shù)組。
  intervalsHeap:    將輸入的intervals數(shù)組加入到這個(gè)小根堆中，左邊緣放高32位，右邊緣放低32位。
  queriesHeap:      將輸入的queries數(shù)組加入到這個(gè)小根堆中，數(shù)值放高32位，下標(biāo)放低32位。
  validHeap:        包含著當(dāng)前position的有效區(qū)間的小根堆，區(qū)間range放高32位，右邊緣放低32位。 */
int *minInterval(int **intervals, int intervalsSize, int *intervalsColSize, int *queries, int queriesSize, int *returnSize)
{
    int x = 0, position = 0, range = 0;
    long int t = 0;
    long int arr1[intervalsSize], arr2[queriesSize], arr3[intervalsSize];
    HeapStruct intervalsHeap, queriesHeap, validHeap;
    int *result = NULL;
    /* 申請(qǐng)結(jié)果數(shù)組的內(nèi)存空間。 */
    result = (int *)malloc(sizeof(int) * queriesSize);
    if(NULL == result)
    {
        *returnSize = 0;
        return result;
    }
    /* 堆空間定義，初始化一開始堆都為空。 */
    intervalsHeap.arr = arr1;
    intervalsHeap.arrSize = 0;
    queriesHeap.arr = arr2;
    queriesHeap.arrSize = 0;
    validHeap.arr = arr3;
    validHeap.arrSize = 0;
    /* 把所有的區(qū)間放入堆中，左邊緣為高優(yōu)先級(jí)，右邊緣為低優(yōu)先級(jí)。 */
    while(intervalsSize > x)
    {
        t = MERGE_LONG(intervals[x][0], intervals[x][1]);
        heapPush(&intervalsHeap, t);
        x++;
    }
    /* 把所有的查詢放入堆中，位置為高優(yōu)先級(jí)，下標(biāo)為低優(yōu)先級(jí)。 */
    x = 0;
    while(queriesSize > x)
    {
        t = MERGE_LONG(queries[x], x);
        heapPush(&queriesHeap, t);
        x++;
    }
    /* 一個(gè)個(gè)查詢逐個(gè)出堆。 */
    while(0 < queriesHeap.arrSize)
    {
        /* 把下標(biāo)和位置列出，然后出堆。 */
        x = GET_LOWER32(queriesHeap.arr[0]);
        position = GET_HIGHER32(queriesHeap.arr[0]);
        heapPop(&queriesHeap);
        /* 把所有左邊緣小于等于position的區(qū)間彈出。 */
        while(0 < intervalsHeap.arrSize && position >= GET_HIGHER32(intervalsHeap.arr[0]))
        {
            /* 右邊緣大于等于position的區(qū)間放到有效堆中（右邊緣小于position的不可能包含當(dāng)前position）。
            這個(gè)有效堆以range為第一優(yōu)先級(jí)，確保堆頂?shù)膮^(qū)間是range最小的。 */
            if(position <= GET_LOWER32(intervalsHeap.arr[0]))
            {
                range = GET_LOWER32(intervalsHeap.arr[0]) - GET_HIGHER32(intervalsHeap.arr[0]) + 1;
                t = MERGE_LONG(range, GET_LOWER32(intervalsHeap.arr[0]));
                heapPush(&validHeap, t);
            }
            heapPop(&intervalsHeap);
        }
        /* 有效堆中，如果堆頂?shù)挠疫吘壭∮趐osition，則彈出。這里用到了延遲刪除的思想。因?yàn)樽钚《训膒op操作只能針對(duì)堆頂。
        上面對(duì)validHeap進(jìn)行push操作之后，堆頂?shù)膮^(qū)間右邊緣值可能已經(jīng)小于當(dāng)前的位置了，這種情況必須pop出去。 */
        while(0 < validHeap.arrSize && position > GET_LOWER32(validHeap.arr[0]))
        {
            heapPop(&validHeap);
        }
        /* 如果此時(shí)的有效堆非空，則當(dāng)前查詢的取值就是堆頂?shù)膮^(qū)間大小，否則就是題目要求的-1。 */
        result[x] = (0 < validHeap.arrSize) ? GET_HIGHER32(validHeap.arr[0]) : INVALID_VALUE;
    }
    /* 返回?cái)?shù)組長(zhǎng)度等于queriesSize。 */
    *returnSize = queriesSize;
    return result;
}

/* 小根堆的push操作。
為確保其保持為一棵完整二叉樹，新push入的數(shù)值初始放到堆尾，然后，根據(jù)父子節(jié)點(diǎn)的大小關(guān)系調(diào)整位置。 */
static void heapPush(HeapStruct *heap, long int t)
{
    int son = heap->arrSize, father = FATHER_NODE(son);
    heap->arrSize++;
    while(INVALID_VALUE != father && heap->arr[father] > t)
    {
        heap->arr[son] = heap->arr[father];
        son = father;
        father = FATHER_NODE(son);
    }
    heap->arr[son] = t;
    return;
}

/* 小根堆的pop操作。
堆頂彈出后，堆頂空缺，為確保其保持為一棵完整二叉樹，將堆尾的數(shù)值補(bǔ)充到堆頂，然后，根據(jù)父子節(jié)點(diǎn)的大小關(guān)系調(diào)整位置。 */
static void heapPop(HeapStruct *heap)
{
    int father = 0, left = LEFT_NODE(father), right = RIGHT_NODE(father), son = 0;
    long int t = heap->arr[heap->arrSize - 1];
    heap->arrSize--;
    while((heap->arrSize > left && heap->arr[left] < t)
        || (heap->arrSize > right && heap->arr[right] < t))
    {
        son = (heap->arrSize > right && heap->arr[right] < heap->arr[left]) ? right : left;
        heap->arr[father] = heap->arr[son];
        father = son;
        left = LEFT_NODE(father);
        right = RIGHT_NODE(father);
    }
    heap->arr[father] = t;
    return;
}

作者：恒等式
鏈接：https://leetcode.cn/problems/minimum-interval-to-include-each-query/solutions/2026632/bao-han-mei-ge-cha-xun-de-zui-xiao-qu-ji-lxkj/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。/* 幾個(gè)全局定義的說明。
  INVALID_VALUE:            無效值-1。小根堆中，根節(jié)點(diǎn)的父節(jié)點(diǎn)使用這個(gè)無效值。題目中結(jié)果數(shù)組里的無效值也是這個(gè)-1。
  FATHER_NODE(x):           小根堆中，每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。其中，根節(jié)點(diǎn)的父節(jié)點(diǎn)是無效值。
  LEFT_NODE(x):             小根堆中，每一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)。當(dāng)它大于等于堆size的時(shí)候無效。
  RIGHT_NODE(x):            小根堆中，每一個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)。當(dāng)它大于等于堆size的時(shí)候無效。
  MERGE_LONG(x, y):         兩個(gè)int數(shù)值合并成一個(gè)long int數(shù)值，其中x占據(jù)高32位，y占據(jù)低32位。
  GET_HIGHER32(x):          獲取一個(gè)long int數(shù)值的高32位值。
  GET_LOWER32(x):           獲取一個(gè)long int數(shù)值的低32位值。 */
#define INVALID_VALUE       -1
#define FATHER_NODE(x)      ((0 == (x)) ? INVALID_VALUE : ((x) - 1 >> 1))
#define LEFT_NODE(x)        (((x) << 1) + 1)
#define RIGHT_NODE(x)       (((x) << 1) + 2)
#define MERGE_LONG(x, y)    ((long int)(x) << 32 | (long int)(y))
#define GET_HIGHER32(x)     ((x) >> 32)
#define GET_LOWER32(x)      ((x) & 0xFFFFFFFF)

/* 小根堆的結(jié)構(gòu)定義，里面包括堆空間數(shù)組arr[]，和堆size。 */
typedef struct
{
    long int *arr;
    int arrSize;
}
HeapStruct;

static void heapPush(HeapStruct *heap, long int t);
static void heapPop(HeapStruct *heap);

/* 主函數(shù)的幾個(gè)變量說明：
  x:                循環(huán)下標(biāo)。
  position:         queries數(shù)組中的數(shù)值。因?yàn)檫@個(gè)數(shù)組會(huì)帶著下標(biāo)一起入堆，在出堆時(shí)，把它的實(shí)際數(shù)值取出到這個(gè)position。
  range:            題目中定義的一個(gè)左閉右閉區(qū)間的大小，等于“右邊緣 - 左邊緣 + 1”。
  t:                long int臨時(shí)數(shù)值。
  arr1,arr2,arr3:   幾個(gè)小根堆中要用到的堆空間數(shù)組。
  intervalsHeap:    將輸入的intervals數(shù)組加入到這個(gè)小根堆中，左邊緣放高32位，右邊緣放低32位。
  queriesHeap:      將輸入的queries數(shù)組加入到這個(gè)小根堆中，數(shù)值放高32位，下標(biāo)放低32位。
  validHeap:        包含著當(dāng)前position的有效區(qū)間的小根堆，區(qū)間range放高32位，右邊緣放低32位。 */
int *minInterval(int **intervals, int intervalsSize, int *intervalsColSize, int *queries, int queriesSize, int *returnSize)
{
    int x = 0, position = 0, range = 0;
    long int t = 0;
    long int arr1[intervalsSize], arr2[queriesSize], arr3[intervalsSize];
    HeapStruct intervalsHeap, queriesHeap, validHeap;
    int *result = NULL;
    /* 申請(qǐng)結(jié)果數(shù)組的內(nèi)存空間。 */
    result = (int *)malloc(sizeof(int) * queriesSize);
    if(NULL == result)
    {
        *returnSize = 0;
        return result;
    }
    /* 堆空間定義，初始化一開始堆都為空。 */
    intervalsHeap.arr = arr1;
    intervalsHeap.arrSize = 0;
    queriesHeap.arr = arr2;
    queriesHeap.arrSize = 0;
    validHeap.arr = arr3;
    validHeap.arrSize = 0;
    /* 把所有的區(qū)間放入堆中，左邊緣為高優(yōu)先級(jí)，右邊緣為低優(yōu)先級(jí)。 */
    while(intervalsSize > x)
    {
        t = MERGE_LONG(intervals[x][0], intervals[x][1]);
        heapPush(&intervalsHeap, t);
        x++;
    }
    /* 把所有的查詢放入堆中，位置為高優(yōu)先級(jí)，下標(biāo)為低優(yōu)先級(jí)。 */
    x = 0;
    while(queriesSize > x)
    {
        t = MERGE_LONG(queries[x], x);
        heapPush(&queriesHeap, t);
        x++;
    }
    /* 一個(gè)個(gè)查詢逐個(gè)出堆。 */
    while(0 < queriesHeap.arrSize)
    {
        /* 把下標(biāo)和位置列出，然后出堆。 */
        x = GET_LOWER32(queriesHeap.arr[0]);
        position = GET_HIGHER32(queriesHeap.arr[0]);
        heapPop(&queriesHeap);
        /* 把所有左邊緣小于等于position的區(qū)間彈出。 */
        while(0 < intervalsHeap.arrSize && position >= GET_HIGHER32(intervalsHeap.arr[0]))
        {
            /* 右邊緣大于等于position的區(qū)間放到有效堆中（右邊緣小于position的不可能包含當(dāng)前position）。
            這個(gè)有效堆以range為第一優(yōu)先級(jí)，確保堆頂?shù)膮^(qū)間是range最小的。 */
            if(position <= GET_LOWER32(intervalsHeap.arr[0]))
            {
                range = GET_LOWER32(intervalsHeap.arr[0]) - GET_HIGHER32(intervalsHeap.arr[0]) + 1;
                t = MERGE_LONG(range, GET_LOWER32(intervalsHeap.arr[0]));
                heapPush(&validHeap, t);
            }
            heapPop(&intervalsHeap);
        }
        /* 有效堆中，如果堆頂?shù)挠疫吘壭∮趐osition，則彈出。這里用到了延遲刪除的思想。因?yàn)樽钚《训膒op操作只能針對(duì)堆頂。
        上面對(duì)validHeap進(jìn)行push操作之后，堆頂?shù)膮^(qū)間右邊緣值可能已經(jīng)小于當(dāng)前的位置了，這種情況必須pop出去。 */
        while(0 < validHeap.arrSize && position > GET_LOWER32(validHeap.arr[0]))
        {
            heapPop(&validHeap);
        }
        /* 如果此時(shí)的有效堆非空，則當(dāng)前查詢的取值就是堆頂?shù)膮^(qū)間大小，否則就是題目要求的-1。 */
        result[x] = (0 < validHeap.arrSize) ? GET_HIGHER32(validHeap.arr[0]) : INVALID_VALUE;
    }
    /* 返回?cái)?shù)組長(zhǎng)度等于queriesSize。 */
    *returnSize = queriesSize;
    return result;
}

/* 小根堆的push操作。
為確保其保持為一棵完整二叉樹，新push入的數(shù)值初始放到堆尾，然后，根據(jù)父子節(jié)點(diǎn)的大小關(guān)系調(diào)整位置。 */
static void heapPush(HeapStruct *heap, long int t)
{
    int son = heap->arrSize, father = FATHER_NODE(son);
    heap->arrSize++;
    while(INVALID_VALUE != father && heap->arr[father] > t)
    {
        heap->arr[son] = heap->arr[father];
        son = father;
        father = FATHER_NODE(son);
    }
    heap->arr[son] = t;
    return;
}

/* 小根堆的pop操作。
堆頂彈出后，堆頂空缺，為確保其保持為一棵完整二叉樹，將堆尾的數(shù)值補(bǔ)充到堆頂，然后，根據(jù)父子節(jié)點(diǎn)的大小關(guān)系調(diào)整位置。 */
static void heapPop(HeapStruct *heap)
{
    int father = 0, left = LEFT_NODE(father), right = RIGHT_NODE(father), son = 0;
    long int t = heap->arr[heap->arrSize - 1];
    heap->arrSize--;
    while((heap->arrSize > left && heap->arr[left] < t)
        || (heap->arrSize > right && heap->arr[right] < t))
    {
        son = (heap->arrSize > right && heap->arr[right] < heap->arr[left]) ? right : left;
        heap->arr[father] = heap->arr[son];
        father = son;
        left = LEFT_NODE(father);
        right = RIGHT_NODE(father);
    }
    heap->arr[father] = t;
    return;
}

到了這里，關(guān)于LeetCode·每日一題·1851. 包含每個(gè)查詢的最小區(qū)間·優(yōu)先隊(duì)列(小頂堆)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！